L(d,1)-labelings of the edge-path-replacement by factorization of graphs

For an integer $d\ge 2$ , an $L(d,1)$ ‐labeling of a graph $G$ is a function $f$ from its vertex set to the non‐negative integers such that $|f(x)-f(y)|\ge d$ if vertices $x$ and $y$ are adjacent, and $|f(x)-f(y)|\ge$ 1 if $x$ and $y$ are at distance two. The minimum span over all the L( $d$ ,1)‐labelings of $G$ is denoted by ${\mathit{\lambda }}_d(G)$ . For a given integer $k\ge 2$ , the edge‐path‐replacement of $G$ or $G(P_k)$ is the graph obtained from $G$ by replacing each edge with a path $P_k$ on $k$ vertices. We show that the edges of $G$ can be colored with $\lceil \mathit{\Delta }(G)/2\rceil$ colors so that each monochromatic subgraph has maximum degree at most 2 and use this fact to establish general upper bounds on ${\mathit{\lambda }}_d(G(P_k))$ for $k\ge 4$ . As a corollary, we settle the following conjecture by Lü (J Comb Optim, 2012): for any graph $G$ with $\mathit{\Delta }(G)\ge$ 2, ${\mathit{\lambda }}_2(G(P_4))\le \mathit{\Delta }(G)$ + 2. Moreover, ${\mathit{\lambda }}_2(G(P_4))=\mathit{\Delta }(G)+1$ when $\mathit{\Delta }(G)$ is even and different from 2. We also show that the class of graphs $G(P_k)$ with $k\ge$ 4 satisfies a conjecture by Havet and Yu (2008 Discrete Math 308:498–513) in the related area of ( $d,1$ )‐total labeling of graphs.