\(L(d, 1)\)-labelings of the edge-multiplicity-path-replacements

Abstract

For a positive integer \(d \geq 1\), an \(L(d, 1)\)-labeling of a graph \(G\) is an assignment of nonnegative integers to \(V(G)\) such that the difference between labels of adjacent vertices is at least \(d\), and the difference between labels of vertices that are distance two apart is at least \(1\). The span of an \(L(d, 1)\)-labeling of a graph \(G\) is the difference between the maximum and minimum integers used by it. The minimum span of an \(L(d, 1)\)-labeling of \(G\) is denoted by \(\lambda(G)\). In [17], we obtained that \(r\Delta + 1 \leq \lambda(G(rP_5)) \leq r\Delta + 2\), \(\lambda(G(rP_k)) = r\Delta + 1\) for \(k \geq 6\); and \(\lambda(G(rP_4)) \leq (\Delta + 1)r + 1\), \(\lambda(G(rP_3)) \leq (\Delta + 1)r + \Delta\) for any graph \(G\) with maximum degree \(\Delta\). In this paper, we will focus on \(L(d, 1)\)-labelings of the edge-multiplicity-path-replacement \(G(rP_k)\) of a graph \(G\) for \(r \geq 2\), \(d \geq 3\), and \(k \geq 3\). And we show that the class of graphs \(G(rP_k)\) with \(k \geq 3\) satisfies the conjecture proposed by Havet and Yu [7].