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}\)-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}(G)\), and prove that the \(\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}\)-numbers and \(\lambda_{2,1}\)-numbers of common classes of graphs, including complete graphs, trees, \(n\)-cubes, and joins.