On the adjacent-vertex-strongly-distinguishing total coloring of graphs |
| |
作者单位: | ZHANG ZhongFu~(1,2) CHENG Hui~(1 ) YAO Bing~1 LI JingWen~3 CHEN XiangEn~1 XU BaoGen~4 1 College of Mathematics and Information Science,Northwest Normal University,Lanzhou,730070,China 2 Institute of Applied Mathematic,Lanzhou Jiaotong University,Lanzhou 730070,China 3 Department of Computer Science,Lanzhou Jiaotong University,Lanzhou 730070,China 4 Department of Mathematics,East China Jiaotong University,Nanchang 330013,China |
| |
摘 要: | For any vertex u∈V(G), let T_N(U)={u}∪{uv|uv∈E(G), v∈v(G)}∪{v∈v(G)|uv∈E(G)}and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C_f(u)={f(x)|x∈TN(U)}. For any two adjacent vertices x and y of V(G)such that C_f(x)≠C_f(y), we refer to f as a k-avsdt-coloring of G("avsdt"is the abbreviation of"adjacent-vertex-strongly- distinguishing total"). The avsdt-coloring number of G, denoted by X_(ast)(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We proveΔ(G) 1≤X_(ast)(G)≤Δ(G) 2 for any tree or unique cycle graph G.
|
收稿时间: | 31 July 2006 |
修稿时间: | 4 July 2007 |
On the adjacent-vertex-strongly-distinguishing total coloring of graphs |
| |
Authors: | Zhang ZhongFu Cheng Hui Yao Bing Li JingWen Chen XiangEn Xu BaoGen |
| |
Institution: | (1) College of Mathematics and Information Science, Northwest Normal University, Lanzhou, 730070, China;(2) Institute of Applied Mathematic, Lanzhou Jiaotong University, Lanzhou, 730070, China;(3) Department of Computer Science, Lanzhou Jiaotong University, Lanzhou, 730070, China;(4) Department of Mathematics, East China Jiaotong University, Nanchang, 330013, China |
| |
Abstract: | For any vertex u ∊ V(G), let T
N
(u) = {u} ∪ {uυ|uυ ∊ E(G), υ ∊ υ(G)} ∪ {υ ∊ υ(G)|uυ ∊ E(G) and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C
f(u) = {f(x) | x ∊ T
N
(u)}. For any two adjacent vertices x and y of V(G) such that C
f(x) ≠ C
f(y), we refer to f as a k-avsdt-coloring of G (“avsdt” is the abbreviation of “ adjacent-vertex-strongly-distinguishing total”). The avsdt-coloring number of G, denoted by χast(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar
graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We prove Δ(G) + 1 ⩽ χast(G) ⩽ Δ(G) + 2 for any tree or unique cycle graph G.
This work was supported by the National Natural Science Foundation of China (Grant Nos. 10771091, 10661007) |
| |
Keywords: | simple connected graph proper coloring adjacent-vertex-strongly-distinguishing total coloring |
本文献已被 CNKI SpringerLink 等数据库收录! |
|