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

Nathaniel Karst (), Jessica Oehrlein (), Denise Sakai Troxell () and Junjie Zhu ()
Additional contact information
Nathaniel Karst: Babson College
Jessica Oehrlein: Franklin W. Olin College of Engineering
Denise Sakai Troxell: Babson College
Junjie Zhu: Franklin W. Olin College of Engineering

Journal of Combinatorial Optimization, 2015, vol. 30, issue 1, No 4, 34-41

Abstract: Abstract 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 ( P k ) is the graph obtained from $$G$$ G by replacing each edge with a path $$P_{k}$$ P k 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 ( P k ) ) for $$k \ge 4$$ k ≥ 4 . As a corollary, we settle the following conjecture by Lü (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 ( P 4 ) ) ≤ Δ ( G ) + 2. Moreover, $$\lambda _{2}(G(P_{4})) = \varDelta (G) + 1$$ λ 2 ( G ( P 4 ) ) = Δ ( G ) + 1 when $$\varDelta (G)$$ Δ ( G ) is even and different from 2. We also show that the class of graphs $$G(P_{k})$$ G ( P k ) 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.

Keywords: L(2 $$; $$; 1)-labeling; L( $$d; $$ d; 1)-labeling; ( $$d; $$ d; 1)-Total labeling; Edge-path-replacement; Factorization of graphs (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9632-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:1:d:10.1007_s10878-013-9632-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9632-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().