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

In this thesis, we study the (d, 1)-total labeling of graphs, which is a special of distance two labeling of graphs motivated by the frequency channel assignment problem. Let G = (V, E) be a finite, simple and undirected graph with the set of vertices V and the set of edges E. A (d, 1)-total labeling 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 numberλ_d^T(G) of a graph G is the least k such that G has a k-(d, 1)- total labeling.In 2002, Havet and Yu^[1] investigated the (d, 1)-total labeling of graphs and conjectured that:λ_d^T(G)≤Δ(G) + 2d - 1, whereΔ(G) denotes the maximum degree of G.This thesis is based on this conjecture.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.In Chapter 2, we study the (2, 1)-total number of trees with sparse vertices of maximum degree is equal to its maximum degree.In Chapter 3, we characterize completely the (2, 1)-total number of the join of two paths. Also we determine the (2, 1)-total number of the join of two cycles C_m∨C_n with an exception that n = m + 1, m≥14 and m = 2,4(mod 12).In Chapter 4, we study the (d,1)-total number of generalized Peterson graph, where d≥3; we also give the (2,1)-total number of Peterson graph.