Distance-two constrained labeling and list-labeling of some graphs

  • Haiying Zhou

Student thesis: Doctoral Thesis


The distance-two constrained labeling of graphs arises in the context of frequency assignment problem (FAP) in mobile and wireless networks. The frequency assignment problem is the problem of assigning frequencies to the stations of a network, so that interference between nearby stations is avoided or minimized while the frequency reusability is exploited. It was first formulated as a graph coloring problem by Hale, who introduced the notion of the T-coloring of a graph, and that attracts a lot of interest in graph coloring. In 1988, Roberts proposed a variation of the channel assignment problem in which “close transmitters must receive different channels and “very close transmitters must receive channels at least two apart. Motivated by this variation, Griggs and Yeh first proposed and studied the L(2, 1)-labeling of a simple graph with a condition at distance two. Because of practical and theoretical applications, the interest for distance-two constrained labeling of graphs is increasing. Since then, many aspects of the problem and related problems remain to be further explored. In this thesis, we first give an upper bound of the L(2, 1)-labeling number, or simply λ number, for a special class of graphs, the n-cubes Qn, where n = 2k k 1. Chang et al. [3] considered a generalization of L(2, 1)-labeling, namely, L(d, 1)- labeling of graphs. We study the L(1, 1)-labeling number of Qn. A lower bound onλ1(Qn) is provided and λ1(Q2k1) is determined. As a related problem, the L(2, 1)-choosability of graphs is studied. Vizing [17] and Erdos et al. [18] generalized the graph coloring problem and introduced the list coloring problem independently more than three decades ago. We shall consider a new variation of the L(2, 1)-labeling problem, the list-L(2, 1)-labeling problem. We determine the L(2, 1)-choice numbers for paths and cycles. We also study the L(2, 1)- choosability for some special graphs such as the Cartesian product graphs and the generalized Petersen graphs. We provide upper bounds of the L(2, 1)-choice numbers for the Cartesian product of a path and a spider, also for the generalized Petersen graphs. Keywords: distance-two labeling, λ-number, L(2, 1)-labeling, L(d, 1)-labeling, list-L(2, 1)-labeling, choosability, L(2, 1)-choice number, path, cycle, n-cube, spider, Cartesian product graph, generalized Petersen graph.

Date of Award2013
Original languageEnglish
SupervisorWai Chee SHIU (Supervisor)

User-Defined Keywords

  • Graph theory
  • Graph labelings


  • Full text is only available for download on campus.

Cite this