The Problem Of (d,1)-Total Labeling In Graphs

In this thesis, we study the (d,1)-total labelling of graphs, which is a special case of distance two labelling of graphs motivated by the frequency channel assignment problem. A (d,1)-total labelling of a graph G is a mapping f from V(G) ∪ E(G) to the label set {0,1, ···,k} such that any two adjacent vertices have different labels, any two adjacent edges have different labels, and any incident vertex and edge have the label difference at least d. The (d,1)-total labelling number λ_d^T(G) of a graph G is the least k such that G has a k-(d,1)-total labelling.In 2002, Havet and Yu investigated the (d,1)-total labelling of graphs and conjectured that, for any graph G, λ_d^T(G) ≤ â–³(G) + 2d - 1. The purpose of this thesis is to confirm this conjecture for some special classes of graphs.In Chapter 1, we collect some basic notions used in the thesis and give a chief survey on this direction. Main results in the thesis are stated.The (2,1)-total number of trees with maximum degree 3 is completely characterized in Chapter 2.In Chapter 3, we study the (2,1)-total labelling of an outerplanar graph G by showing the following:(1) λ₂^T(G)≤4 if â–³(G)≤2;(2) λ₂^T(G)≤5 if â–³(G)=3 and G is 2-connected;(3) λ₂^T(G)≤6 if â–³(G) = 4, G is 2-connected and has no open n-gears for n ≥ 4;(4) λ₂^T(G)≤△(G) + 2 if â–³(G) ≥ 5.The (2,1)-total labelling number of product of two paths or two cycles is determined in Chapter 4.