Labeling Dot-Cartesian and Dot-Lexicographic Product Graphs with a Condition at Distance Two
Zhendong Shao, Igor Averbakh, Sandi Klavžar · The Computer Journal · 2015
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.