Three problems in graph labeling

An r-labeling of graph G is a function Φ : V(G) $\mid \to$ {lcub}1, 2, ..., r{rcub}. In this dissertation, we consider three problems that involve labeling the vertices of a graph so that a set of conditions are satisfied. We are also interested in the minimum number of label types or colors needed to achieve the said conditions.; Suppose G is labeled by Φ. Let (G, Φ) denote the labeled version of G. The labeling Φ is said to be distinguishing if the only label-preserving automorphism of (G, Φ) is the identity map. The distinguishing number of G, D(G), is the minimum number of colors needed so that G has a distinguishing labeling. The complexity of the problem “Is D(G) ≤ k?” is as difficult as the Graph Automorphism Problem when k = 1 and may or may not be in NP nor co-NP when k ≥ 2.; In Chapter 2, we characterize the distinguishing labelings of rooted trees and show how we can use this result to find their distinguishing numbers. We then present two polynomial-time algorithms that solve for the distinguishing numbers of trees and forests. Thus, in this sense, determining if D(G) ≤ k when G is a tree or a forest is easy.; In Chapter 3, we generalize distinguishing labelings and numbers to i-local distinguishing labelings and numbers of a graph. If υ is a vertex in G, let $Niu$ denote the induced subgraph of G that contains all the vertices that are at most distance i away from υ and has υ as its root. A labeling, Φ, is i-local distinguishing if for every pair of vertices (u, υ) in G, the labeled versions of $Niu$ and $Niu$ are non-isomorphic. We note that i-local distinguishing labelings are distinguishing labelings too for all i ≥ 1. We determine or provide good upper bounds for the i-local distinguishing numbers of cycles and trees when i ≥ 1 and n is sufficiently large. We also give an upper bound for the 1-local distinguishing numbers of almost all graphs.; In Chapter 4, we consider a problem known as the demand routing and slotting problem with unit demands (or unit-DRSP) on rings (or cycles). A demand on a ring is an ordered pair (source, destination ). Given a set of demands on a ring, each demand must be routed either clockwise or counterclockwise and each route must be assigned a slot so that two routes that go through the same edge of the ring are assigned different slots. In unit-DRSP, we are interested in finding the minimum number of slots needed so that the two tasks we mentioned are accomplished. The slotting component of the problem can be reduced to the graph coloring problem on circular arc graphs.; Unit-DRSP is known to be NP-hard. The best approximation algorithm has a factor of 2. If the optimal solution is large, Kumar [25] has a 1.68-approximation algorithm. We present a (2 − 1/O (log n))-approximation algorithm that holds in general.