×

\(L(d,1)\)-labelings of the edge-multiplicity-path-replacements. (English) Zbl 1424.05255

Summary: 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_d(G)\). D. Lü and J. Sun [J. Comb. Optim. 31, No. 1, 396–404 (2016; Zbl 1341.90136)] 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 focus on the \(L(d,1)\)-labelings-number of the edge-multiplicity-path-replacement \(G(rP_k)\) of a graph \(G\) for \(r\geq 2\), \(d\geq 3\) and \(k\geq 3\). We show that the class of graphs \(G(rP_k)\) with \(k\geq 3\) satisfies the conjecture proposed by F. Havet and M.-L. Yu [\((d,1)\)-total labelling of graphs. Techn. Rep. RR-4650, INRIA (2002)].

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)

Citations:

Zbl 1341.90136