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.
| Identifer | oai:union.ndltd.org:hkbu.edu.hk/oai:repository.hkbu.edu.hk:etd_ra-2553 |
| Date | 01 January 2013 |
| Creators | Zhou, Haiying |
| Publisher | HKBU Institutional Repository |
| Source Sets | Hong Kong Baptist University |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Restricted Access Theses and Dissertations |
| Rights | The author retains all rights to this work. The author has signed an agreement granting HKBU a non-exclusive license to archive and distribute their thesis. |
Page generated in 0.0158 seconds