Edge Labelings with a Condition at Distance Two

Abstract

For graph $G$ with non-empty edge set, a $(j,k)$-edge labeling of $G$ is an integer labeling of the edges such that adjacent edges receive labels that differ by at least $j$, and edges which are distance two apart receive labels that differ by at least $k$. The ${\lambda }_{j,k}^{\prime }$-number of $G$ is the minimum span over the $(j,k)$-edge labelings of $G$. By establishing the equivalence of the edge labelings of $G$ to particular vertex labelings of $G$ and the line graph of $G$, we explore the properties of ${\chi }_{j,k}(G)$. In particular, we obtain bounds on ${\lambda }_{j,k}^{\prime }(G)$, and prove that the ${\mathrm{\Delta }}^2$ conjecture of Griggs and Yeh is true for graph $H$ if $H$ is the line graph of some graph $G$. We investigate the ${\lambda }_{1,1}^{\prime }$-numbers and ${\lambda }_{2,1}$-numbers of common classes of graphs, including complete graphs, trees, $n$-cubes, and joins.