Electronic Thesis and Dissertation Repository


Doctor of Philosophy


Computer Science


Dr. Roberto Solis-Oba


The L(2,1) -labeling problem has been extensively researched on many graph classes. In this thesis, we have also studied the problem on some particular classes of graphs.

In Chapter 2 we present a new general approach to derive upper bounds for L(2,1)-labeling numbers and applied that approach to derive bounds for the four standard graph products.

In Chapter 3 we study the L(2,1)-labeling number of the composition of n graphs.

In Chapter 4 we consider the Cartesian sum of graphs and derive, both, lower and upper bounds for their L(2,1)-labeling number. We use two different approaches to derive the upper bounds and both approaches improve previously known bounds. We also present new approximation algorithms for the L(2,1 )-labeling problem on Cartesian sum graphs.

In Chapter 5, we characterize d-disk graphs for d>1, and give the first upper bounds on the L(2,1)-labeling number for this class of graphs.

In Chapter 6, we compute upper bounds for the L(2,1)-labeling number of total graphs of K_{1,n}-free graphs.

In Chapter 7, we study the four standard products of graphs using the adjacency matrix analysis approach.

In Chapter 8, we determine the exact value for the L(2,1)-labeling number of a particular class of Mycielski graphs. We also provide, both, lower and upper bounds for the L(2,1)-labeling number of any Mycielski graph.