Vertex-distinguishing IE-total Colorings of Cycles and Wheels

Let G be a simple graph. An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C（u） be the set of colors of vertex u and edges incident to u under f. For an IE-total coloring f of G using k colors, if C（u）=C（v） for any two different vertices u and v of V （G）, then f is called a k-vertex-distinguishing IE-total-coloring of G, or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt（G）, and is called the VDIET chromatic number of G. We get the VDIET chromatic numbers of cycles and wheels, and propose related conjectures in this paper.

Vertex-distinguishing VE-total Colorings of Cycles and Complete Graphs

Let G be a simple graph of order at least 2.A VE-total-coloring using k colors of a graph G is a mapping f from V (G) E(G) into {1,2,···,k} such that no edge receives the same color as one of its endpoints.Let C(u)={f(u)} {f(uv) | uv ∈ E(G)} be the color-set of u.If C(u)=C(v) for any two vertices u and v of V (G),then f is called a k-vertex-distinguishing VE-total coloring of G or a k-VDVET coloring of G for short.The minimum number of colors required for a VDVET coloring of G is denoted by χ ve vt (G) and it is called the VDVET chromatic number of G.In this paper we get cycle C n,path P n and complete graph K n of their VDVET chromatic numbers and propose a related conjecture.

Vertex-distinguishing E-total Coloring of Complete Bipartite Graph K 7,n when7≤n≤95

Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C（x） denote the set of colors of vertex x and of the edges incident with x, we call C（x） the color set of x. If C（u） ≠ C（v） for any two different vertices u and v of V （G）, then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by Хvt^e（G） and is called the VDE T chromatic number of G. The VDET coloring of complete bipartite graph K7,n （7 ≤ n ≤ 95） is discussed in this paper and the VDET chromatic number of K7,n （7 ≤ n ≤ 95） has been obtained.

On the adjacent vertex-distinguishing acyclic edge coloring of some graphs

A proper edge coloring of a graph G is called adjacent vertex-distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the coloring set of edges incident with u is not equal to the coloring set of edges incident with v, where uv∈ E（G）. The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by X＇Aa（G）, is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. If a graph G has an adjacent vertex distinguishing acyclic edge coloring, then G is called adjacent vertex distinguishing acyclic. In this paper, we obtain adjacent vertex-distinguishing acyclic edge coloring of some graphs and put forward some conjectures.

Adjacent Vertex-distinguishing E-total Coloring on Some Join Graphs Cm ∨ Gn

Let G(V, E) be a simple connected graph and k be positive integers. A mapping f from V∪E to {1, 2, ··· , k} is called an adjacent vertex-distinguishing E-total coloring of G(abbreviated to k-AVDETC), if for uv ∈ E(G), we have f(u) ≠ f(v), f(u) ≠ f(uv), f(v) ≠ f(uv), C(u) ≠C(v), where C(u) = {f(u)}∪{f(uv)|uv ∈ E(G)}. The least number of k colors required for which G admits a k-coloring is called the adjacent vertex-distinguishing E-total chromatic number of G is denoted by x^e_(at) (G). In this paper, the adjacent vertexdistinguishing E-total colorings of some join graphs C_m∨G_n are obtained, where G_n is one of a star S_n , a fan F_n , a wheel W_n and a complete graph K_n . As a consequence, the adjacent vertex-distinguishing E-total chromatic numbers of C_m∨G_n are confirmed.

Vertex-distinguishing IE-total Colorings of Complete Bipartite Graphs K8,n

Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χ_(vt)^(ie) (G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K_(8,n)are discussed in this paper. Particularly, the VDIET chromatic number of K_(8,n) are obtained.

ON EQUITABLE VERTEX DISTINGUISHING EDGE COLORINGS OF TREES

It has been known that determining the exact value of vertex distinguishing edge index X ＇8（G） of a graph G is difficult, even for simple classes of graphs such as paths, cycles, bipartite complete graphs, complete, graphs, and graphs with maximum degree 2. Let rid（G） denote the number of vertices of degree d in G, and let X＇es（G） be the equitable vertex distinguishing edge index of G. We show that a tree T holds nl （T） ≤ X ＇s （T） ≤ n1 （T） ＋ 1 and X＇s（T） = X＇es（T） if T satisfies one of the following conditions （i） n2（T） ≤△（T） or （ii） there exists a constant c with respect to 0 〈 c 〈 1 such that n2（T） △ cn1（T） and ∑3 ≤d≤△（T）nd（T） ≤ （1 - c）n1（T） ＋ 1.

Adjacent Vertex Distinguishing Total Coloring of M（Tn）

如果为任何东西二个邻近的顶点有不同颜色 sets.According 到树的性质， G 的 k 合适的全部的着色被称为邻近的区分，区分全部的色彩的数字的邻近的顶点将用方法为树的 Mycielski 图被决定感应。

Smarandachely Adjacent-vertex-distinguishing Proper Edge Coloring ofK4 ∨ Kn

Let f be a proper edge coloring of G using k colors.For each x∈V(G),the set of the colors appearing on the edges incident with x is denoted by S_f(x)or simply S(x)if no confusion arise.If S(u)■S(v)and S(v)■S(u)for any two adjacent vertices u and v,then f is called a Smarandachely adjacent vertex distinguishing proper edge coloring using k colors,or k-SA-edge coloring.The minimum number k for which G has a Smarandachely adjacent-vertex-distinguishing proper edge coloring using k colors is called the Smarandachely adjacent-vertex-distinguishing proper edge chromatic number,or SAedge chromatic number for short,and denoted byχ'_(sa)(G).In this paper,we have discussed the SA-edge chromatic number of K_4∨K_n.

Adjacent Vertex Distinguishing I-total Coloring of Outerplanar Graphs

Let G be a simple graph with no isolated edge. An/-total coloring of a graphG is a mapping Ф ： V（G） U E（G） → （1, 2,…… , k） such that no adjacent vertices receive thesame color and no adjacent edges receive the same color. An/-total coloring of a graph G issaid to be adjacent vertex distinguishing if for any pair of adjacent vertices u and v of G, wehave CФ（u） ≠ CФ（v）, where CФ（u） denotes the set of colors of u and its incident edges. Theminimum number of colors required for an adjacent vertex distinguishing I-total coloring of GG is called the adjacent vertex distinguishing I-total chromatic number, denoted by Xat（G）.In this paper, we characterize the adjacent vertex distinguishing I-total chromatic numberof outerplanar graphs.

单圈图的邻点全和可区别全染色

用结构分析法完整刻画单圈图U的邻点全和可区别全染色,并得到当U■C_(n)且n■0(mod 3)时,ftndiΣ(U)=Δ(U)+2;其他情况下,ftndiΣ(U)=Δ(U)+1.表明邻点全和可区别全染色猜想在任意单圈图上都成立.

等完全p-部图的点被多重集可区别的一般全染色

利用反证法、色集合事先分配法和构造染色法,讨论等完全p-部图的顶点被多重集可区别的一般全染色,给出最优染色方案,并确定相应染色的色数.

三类联图的2-距离和可区别边染色

该文探讨了C_(m)·P_(n)、C_(m)·S_(n)和C_(m)·K_(n)三类联图的2-距离和可区别边染色问题.根据联图的结构特点,利用组合分析法、反证法以及分类讨论思想,得到了这三类联图的2-距离和可区别边色数.结论表明三类联图的2-距离和可区别边色数均不超过Δ+2.

一些特殊图的中间图的2-距离和可区别全染色

为了进一步研究图的2-距离和可区别全染色问题,根据中间图的构造特点,通过构造染色函数,利用组合分析法得到了路,圈,星,扇,轮,双星以及轮环图的中间图的2-距离和可区别全色数.

圈与路的点被多重集可区别的E-全染色

图G的E-全染色是指使得相邻顶点染以不同色,每条边与它的端点染以不同的颜色的全染色.设f是图G的E-全染色,图G的一个顶点x在f下的多重色集合C˜(x)是指点x的颜色以及与x关联的边的颜色构成的多重集.若图G的任意两个不同顶点在f下的多重色集合不同,则f称为图G的点被多重集可区别的E-全染色.对图G进行点被多重集可区别的E-全染色所需用的最少的颜色的数目叫做G的点被多重集可区别的E-全色数.利用反证法和构造具体染色的方法,讨论了圈与路的点被多重集可区别的E-全染色问题,给出了圈与路的最优的点被多重集可区别的E-全染色方案,并确定了圈与路的点被多重集可区别的E-全色数.

一类稀疏图的邻和可区别全染色

利用组合零点定理和权转移法,研究了一类稀疏图的邻和可区别全染色,证明了这类图的邻和可区别全色数不超过Δ+3,得到了邻和可区别全色数猜想对这类稀疏图是成立的。

Upper bounds on vertex distinguishing chromatic index of some Halin graphs

A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph C is denoted by Xs＇8（G）. In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with △（G） ≥ 4, respectively.

GRAPH COLORING BASED CHANNEL ASSIGNMENT FRAMEWORK FOR RURAL WIRELESS MESH NETWORKS

IEEE 802.11 based wireless mesh networks with directional antennas are expected to be a new promising technology and an economic approach for providing wireless broadband services in rural areas.In this paper,we discuss interference models and address how they can affect the design of channel assignment in rural mesh networks.We present a new channel assignment framework based on graph coloring for rural wireless mesh networks.The goal of the framework is to allow synchronously transmitting or receiving data from multiple neighbor links at the same time,and continuously doing full-duplex data transfer on every link,creating an efficient rural mesh network without interference.Channel assignment is shown to be NP-hard.We frame this channel allocation problem in terms of Adjacent Vertex Distinguishing Edge Coloring(AVDEC).Detailed assignment results on grid topology are presented and discussed.Furthermore,we design an algorithm.Finally,we evaluate the performance of the proposed algorithm through extensive simulations and show the algorithm is effective to the regular grid topologies,and the number of colors used by the algorithm is upper bounded by+1.Hence the algorithm guarantees that the number of channels available in standards such as IEEE802.11a is sufficient to have a valid AVDEC for many grid topologies.We also evaluate the proposed algorithm for arbitrary graphs.The algorithm provides a lower upper bound on the minimum number of channels to the AVDEC index channel assignment problem.

Neighbor Sum Distinguishing Index of Graphs with Maximum Average Degree

A proper k-edge coloring of a graph G = (V(G), E(G)) is an assignment c: E(G) → {1, 2, …, k} such that no two adjacent edges receive the same color. A neighbor sum distinguishing k-edge coloring of G is a proper k-edge coloring of G such that for each edge uv ∈ E(G). The neighbor sum distinguishing index of a graph G is the least integer k such that G has such a coloring, denoted by χ’Σ(G). Let be the maximum average degree of G. In this paper, we prove χ’Σ(G) ≤ max{9, Δ(G) +1} for any normal graph G with . Our approach is based on the discharging method and Combinatorial Nullstellensatz.