Publication Date:
2016-01-08
Description:
If $d(x,y)$ denotes the distance between vertices $x$ and $y$ in a graph $G$ , then an $L(2,1)$ -labeling of a graph $G$ is a function $f$ from vertices of $G$ to nonnegative integers such that $\boldsymbol {\vert f(x) - f(y)\vert \ge 2}$ if $\boldsymbol {d(x,y) = 1}$ , and $\boldsymbol {\vert f(x) - f(y)\vert \ge 1}$ if $\boldsymbol {d(x,y) = 2}$ . Griggs and Yeh conjectured that for any graph with maximum degree $\boldsymbol {\Delta \ge 2}$ , there is an $\boldsymbol {L(2,1)}$ -labeling with all labels not greater than $\boldsymbol {\Delta ^2}$ . We prove that the conjecture holds for dot-Cartesian products and dot-lexicographic products of two graphs with possible minor exceptions in some special cases. The bounds obtained are in general much better than the $\boldsymbol {\Delta ^2}$ -bound.
Print ISSN:
0010-4620
Electronic ISSN:
1460-2067
Topics:
Computer Science
Permalink
