published_or_final_version / abstract / Mathematics / Master / Master of Philosophy

Thesis (M. Phil.)--University of Hong Kong, 2007. / Title proper from title frame. Also available in printed format.

Let $l$ be a graceful label of a graceful graph $G$ with $n$ nodes. We outline a procedure to generate a graceful label $l$ and its graph $G$ by constructing a sequence of labeled edges $(a_k)_{k=1}^{n-1}$ where the $k$th term of the sequence corresponds to an edge labeled $k$. We use the complement of the label generated to identify a class of transformations on graceful labels that can produce additional graceful labelings on $G$. We then identify a subset of labels generated this way with properties that limit the number of graceful labels such a graph can have and study some properties of those labels. We prove that all edge-preserving transformations of these labels fix over half of all node labels, and after establishing criteria necessary for such a transformation to leave some node labels unfixed, we show that for $n\leq9$ these transformations fix all node labels.

No description available.

No description available.

No description available.

No description available.

No description available.

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.

No description available.