Lambda number for the direct product of some family of graphs

Byeong Moon Kim (), Yoomi Rho () and Byung Chul Song ()
Additional contact information
Byeong Moon Kim: Gangneung-Wonju National University
Yoomi Rho: Incheon National University
Byung Chul Song: Gangneung-Wonju National University

Journal of Combinatorial Optimization, 2017, vol. 33, issue 4, No 5, 1257-1265

Abstract: Abstract An L(2, 1)-labeling for a graph $$G=(V,E)$$ G = ( V , E ) is a function f on V such that $$|f(u)-f(v)|\ge 2$$ | f ( u ) - f ( v ) | ≥ 2 if u and v are adjacent and f(u) and f(v) are distinct if u and v are vertices of distance two. The L(2, 1)-labeling number, or the lambda number $$\lambda (G)$$ λ ( G ) , for G is the minimum span over all L(2, 1)-labelings of G. When $$P_{m}\times C_{n}$$ P m × C n is the direct product of a path $$P_m$$ P m and a cycle $$C_n$$ C n , Jha et al. (Discret Appl Math 145:317–325, 2005) computed the lambda number of $$P_{m}\times C_{n}$$ P m × C n for $$n\ge 3$$ n ≥ 3 and $$m=4,5$$ m = 4 , 5 . They also showed that when $$m\ge 6$$ m ≥ 6 and $$n\ge 7$$ n ≥ 7 , $$\lambda (P_{m}\times C_{n})=6$$ λ ( P m × C n ) = 6 if and only if n is the multiple of 7 and conjectured that it is 7 if otherwise. They also showed that $$\lambda (C_{7i}\times C_{7j})=6$$ λ ( C 7 i × C 7 j ) = 6 for some i, j. In this paper, we show that when $$m\ge 6$$ m ≥ 6 and $$n\ge 3$$ n ≥ 3 , $$\lambda (P_m\times C_n)=7$$ λ ( P m × C n ) = 7 if and only if n is not a multiple of 7. Consequently the conjecture is proved. Here we also provide the conditions on m and n such that $$\lambda (C_m\times C_n)\le 7$$ λ ( C m × C n ) ≤ 7 .

Keywords: Lambda number; Channel assignment problem; Paths and cycles; Direct product; 05C15; 05C78; 05C38 (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0032-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:33:y:2017:i:4:d:10.1007_s10878-016-0032-x

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

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