首页 | 本学科首页   官方微博 | 高级检索  
     检索      

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 uV(G), let T N (u) = {u} ∪ {|E(G), υυ(G)} ∪ {υυ(G)|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) | xT 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号