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

Autor: Nathaniel J. Karst, Denise Sakai Troxell, Jessica Oehrlein, Junjie Zhu
Rok vydání: 2013
Předmět:
Zdroj: Journal of Combinatorial Optimization. 30:34-41
ISSN: 1573-2886
1382-6905
DOI: 10.1007/s10878-013-9632-x
Popis: For an integer $$d \ge 2$$d?2, an $$L(d$$L(d,1)-labeling of a graph $$G$$G is a function $$f$$f from its vertex set to the non-negative integers such that $${\vert }f(x) - f(y){\vert } \ge d$$|f(x)?f(y)|?d if vertices $$x$$x and $$y$$y are adjacent, and $${\vert }f(x) - f(y){\vert } \ge $$|f(x)?f(y)|? 1 if $$x$$x and $$y$$y are at distance two. The minimum span over all the L($$d$$d,1)-labelings of $$G$$G is denoted by $$\lambda _{d}(G)$$?d(G). For a given integer $$k \ge 2$$k?2, the edge-path-replacement of$$G$$G or $$G(P_{k})$$G(Pk) is the graph obtained from $$G$$G by replacing each edge with a path $$P_{k}$$Pk on $$k$$k vertices. We show that the edges of $$G$$G can be colored with $$\lceil \varDelta (G)/2\rceil $$?Δ(G)/2? colors so that each monochromatic subgraph has maximum degree at most 2 and use this fact to establish general upper bounds on $$\lambda _{d}(G(P_{k}))$$?d(G(Pk)) for $$k \ge 4$$k?4. As a corollary, we settle the following conjecture by Lu (J Comb Optim, 2012): for any graph $$G$$G with $$\varDelta (G) \ge $$Δ(G)? 2, $$\lambda _{2}(G(P_{4})) \le \varDelta (G)$$?2(G(P4))≤Δ(G) + 2. Moreover, $$\lambda _{2}(G(P_{4})) = \varDelta (G) + 1$$?2(G(P4))=Δ(G)+1 when $$\varDelta (G)$$Δ(G) is even and different from 2. We also show that the class of graphs $$G(P_{k})$$G(Pk) with $$k \ge $$k? 4 satisfies a conjecture by Havet and Yu (2008 Discrete Math 308:498---513) in the related area of ($$d,1$$d,1)-total labeling of graphs.
Databáze: OpenAIRE
Externí odkaz: