List (d,1)-total labelling of graphs embedded in surfaces

• 1、School of Mathematics,Shandong University, JiNan 250100

Abstract：A k-(d,1)-total labelling of a graph G is afunction c from V(G)∪E(G) to the color set {0,1,...,k} such that c(u) ≠c(v) if uv∈E(G),c(e)≠c(e') if e and e' are two adjacent edges, and |c(u)-c(e)|≥d if vertex u is incident to the edge e. Theminimum k such that G has a k-(d,1)-total labelling iscalled the (d,1)-total labelling number and denoted by λTd(G).Suppose that L(x) is a list of colors available to choose for eachelement x∈V(G)∪E(G). If G has a (d,1)-total labellingc such that c(x)∈L(x) for all x∈V(G)∪E(G), then wesay that c is an L-(d,1)-total labelling of G, and G is L-(d,1)-total labelable. The list (d,1)-totallabelling number, denoted by Ch T d,1(G), is the minimum k suchthat G is k-(d,1)-total labelable. In this paper, we prove that the list (d,1)-total labelling number of a graph embedded in a surface with Euler characteristic ε whose maximum degree Δ(G) is sufficiently large is at most Δ(G)+2d.

keywords： graph theory (d,1)-total labelling list (d,1)-total labelling list (d,1)-total labelling number

点击查看论文中文信息

点击收起