#### Vol. 8, No. 4, 2015

 Recent Issues
 The Journal About the Journal Subscriptions Editorial Board Editors’ Interests Scientific Advantages Submission Guidelines Submission Form Ethics Statement Editorial Login Author Index Coming Soon Contacts ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print)
The $\Delta^2$ conjecture holds for graphs of small order

### Cole Franks

Vol. 8 (2015), No. 4, 541–549
##### Abstract

An $L\left(2,1\right)$-labeling of a simple graph $G$ is a function $f:V\left(G\right)\to ℤ$ such that if $xy\in E\left(G\right)$, then $|f\left(x\right)-f\left(y\right)|\ge 2$, and if the distance between $x$ and $y$ is two, then $|f\left(x\right)-f\left(y\right)|\ge 1$. $L\left(2,1\right)$-labelings are motivated by radio channel assignment problems. Denote by ${\lambda }_{2,1}\left(G\right)$ the smallest integer such that there exists an $L\left(2,1\right)$-labeling of $G$ using the integers $\left\{0,\dots ,{\lambda }_{2,1}\left(G\right)\right\}$. We prove that ${\lambda }_{2,1}\left(G\right)\le {\Delta }^{2}$, where $\Delta =\Delta \left(G\right)$, if the order of $G$ is no greater than $\left(⌊\Delta ∕2⌋+1\right)\left({\Delta }^{2}-\Delta +1\right)-1$. This shows that for graphs no larger than the given order, the 1992 “${\Delta }^{2}$ conjecture” of Griggs and Yeh holds. In fact, we prove more generally that if $L\ge {\Delta }^{2}+1$, $\Delta \ge 1$, and

$|V\left(G\right)|\le \left(L-\Delta \right)\left(⌊\frac{L-1}{2\Delta }⌋+1\right)-1,$

then ${\lambda }_{2,1}\left(G\right)\le L-1$. In addition, we exhibit an infinite family of graphs with ${\lambda }_{2,1}\left(G\right)={\Delta }^{2}-\Delta +1$.

##### Keywords
L(2,1)-labeling, graph labeling, channel assignment
Primary: 97K30