IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Graph Labeling with Distance Conditions

  • April 25, 2013
  • 2:15 p.m.
  • LeConte 312


An $L({2,1})$-labeling of a simple graph $G$ is a function $f:V(G) \rightarrow \mathbb{Z}$ such that if $xy \in E(G)$, then $|f(x) - f(y)| \geq 2$ and if the shortest path in $G$ connecting $x$ and $y$ has two edges then $|f(x) - f(y)| \geq 1$. The $L(2,1)$-labeling problem is an example of a Channel Assignment Problem, which aims to model the frequency assignment of transmitters which could interfere when near. The objective is generally to minimize the difference between the highest and lowest label used, called the span. The $L(2,1)$-labeling problem was posed by Jerrold Griggs and Roger Yeh in 1992, and they conjectured that any graph has a labelling with span no greater than the square of the maximum degree. The author will present his result that if the order of $G$ is at most $(\lfloor \Delta/2 \rfloor + 1 )(\Delta^2 - \Delta+ 1) - 1$, then $G$ has a labeling with span no greater than $\Delta^2$, where $\Delta = \Delta(G)$ is the maximum degree of the graph. This shows that for graphs no larger than the given order, the 1992 ``$\Delta^2$ Conjecture" of Griggs and Yeh holds. In addition, the author will show that there is a polynomial time algorithm to find $L(2,1)$-labelings with span and order satisfying the conditions above.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster