On the adjacent-vertex-strongly-distinguishing total coloring of graphs

• 来源期刊: 中国科学A辑(英文版)
• 年，卷（期）: 2008,（3）
• 页码范围: 427-436
• 页数: 10页
• 语种: 英文
• DOI: 10.1007/s11425-007-0128-y

摘要

For any vertex u∈V(G), let TN(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 Cf(u) = {f(x) | x ∈ TN(u)}. For any two adjacent vertices x and y of V(G) such that Cf(x) ≠ Cf(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.