L(2,1)-labelings of the edge-multiplicity-paths-replacement of a graph

Damei Lü () and Jianping Sun
Additional contact information
Damei Lü: Nantong University
Jianping Sun: Nantong University

Journal of Combinatorial Optimization, 2016, vol. 31, issue 1, No 26, 396-404

Abstract: Abstract An L(2,1)-labeling of a graph $$G$$ G is an assignment of nonnegative integers to $$V(G)$$ V ( G ) such that the difference between labels of adjacent vertices is at least $$2$$ 2 , and the difference between labels of vertices that are distance two apart is at least 1. The span of an L(2,1)-labeling of a graph $$G$$ G is the difference between the maximum and minimum integers used by it. The minimum span of an L(2,1)-labeling of $$G$$ G is denoted by $$\lambda (G)$$ λ ( G ) . This paper focuses on L(2,1)-labelings-number of the edge-multiplicity-paths-replacement $$G(rP_{k})$$ G ( r P k ) of a graph $$G$$ G . In this paper, we obtain that $$ r\Delta +1 \le \lambda (G(rP_{5}))\le r\Delta +2$$ r Δ + 1 ≤ λ ( G ( r P 5 ) ) ≤ r Δ + 2 , $$\lambda (G(rP_{k}))= r\Delta +1$$ λ ( G ( r P k ) ) = r Δ + 1 for $$k\ge 6$$ k ≥ 6 ; and $$\lambda (G(rP_{4}))\le (\Delta +1)r+1$$ λ ( G ( r P 4 ) ) ≤ ( Δ + 1 ) r + 1 , $$\lambda (G(rP_{3}))\le (\Delta +1)r+\Delta $$ λ ( G ( r P 3 ) ) ≤ ( Δ + 1 ) r + Δ for any graph $$G$$ G with maximum degree $$\Delta $$ Δ . And the L(2,1)-labelings-numbers of the edge-multiplicity-paths-replacement $$G(rP_{k})$$ G ( r P k ) are completely determined for $$1\le \Delta \le 2$$ 1 ≤ Δ ≤ 2 . And we show that the class of graphs $$G(rP_{k})$$ G ( r P k ) with $$k\ge 3 $$ k ≥ 3 satisfies the conjecture: $$\lambda ^{T}_{2}(G)\le \Delta +2$$ λ 2 T ( G ) ≤ Δ + 2 by Havet and Yu (Technical Report 4650, 2002).

Keywords: Channel assignment; L(2; 1)-labeling; The edge-multiplicity-paths-replacement (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9761-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:31:y:2016:i:1:d:10.1007_s10878-014-9761-x

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

DOI: 10.1007/s10878-014-9761-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 ().