n-fold L(2, 1)-labelings of Cartesian product of paths and cycles

Fei-Huang Chang (), Ma-Lian Chia (), Shih-Ang Jiang (), David Kuo () and Jing-Ho Yan ()
Additional contact information
Fei-Huang Chang: National Taiwan Normal University
Ma-Lian Chia: Aletheia University
Shih-Ang Jiang: National Dong Hwa University
David Kuo: National Dong Hwa University
Jing-Ho Yan: Aletheia University

Journal of Combinatorial Optimization, 2024, vol. 47, issue 3, No 9, 16 pages

Abstract: Abstract For two sets of nonnegative integers A and B, the distance between these two sets, denoted by d(A, B), is defined by $$d(A,B)=\min \{|a-b|:a\in A,b\in B\}$$ d ( A , B ) = min { | a - b | : a ∈ A , b ∈ B } . For a positive integer n, let $$S_{n}$$ S n denote the family $$ \{X:X\subseteq {\mathbb {N}} \cup \{0\},|X|=n\}$$ { X : X ⊆ N ∪ { 0 } , | X | = n } . Given a graph G and positive integers n, p and q, an n-fold L(p, q)-labeling of G is a function $$f:V(G)\rightarrow S_{n} $$ f : V ( G ) → S n satisfies $$d(f(u),f(v))\ge p$$ d ( f ( u ) , f ( v ) ) ≥ p if $$d_{G}(u,v)=1$$ d G ( u , v ) = 1 , and $$ d(f(u),f(v))\ge q$$ d ( f ( u ) , f ( v ) ) ≥ q if $$d_{G}(u,v)=2$$ d G ( u , v ) = 2 . An n-fold k-L(p, q)-labeling f of G is an n-fold L(p, q)-labeling of G with the property that $$\max \{a:a\in \bigcup _{u\in V(G)}f(u)\}\le k$$ max { a : a ∈ ⋃ u ∈ V ( G ) f ( u ) } ≤ k . The smallest number k to guarantee that G has an n-fold k-L(p, q)-labeling is called the n -fold L(p, q)-labeling number of G and is denoted by $$\lambda _{p,q}^{n}(G)$$ λ p , q n ( G ) . When $$p=2, $$ p = 2 , $$q=1,$$ q = 1 , we use $$\lambda ^{n}(G)$$ λ n ( G ) to replace $$ \lambda _{2,1}^{n}(G)$$ λ 2 , 1 n ( G ) for simplicity. We study the n-fold L(2, 1) -labeling numbers of Cartesian product of paths and cycles in this paper. We give a necessary and sufficient condition for $$\lambda ^{n}(C_{m}\square P_{2})$$ λ n ( C m □ P 2 ) equals $$4n+1.$$ 4 n + 1 . Based on this, we determine the exact value of $$ \lambda ^{2}(C_{m}\square P_{2})$$ λ 2 ( C m □ P 2 ) (except for $$m=5,6$$ m = 5 , 6 and 9) and $$\lambda ^{3}(C_{m}\square P_{2})$$ λ 3 ( C m □ P 2 ) (except for $$m=5,6,9,10,13$$ m = 5 , 6 , 9 , 10 , 13 and 17). We also give bounds for $$\lambda ^{n}(C_{m}\square P_{k})$$ λ n ( C m □ P k ) when n, m satisfy certain conditions, and from this, we obtain the exact value of $$\lambda ^{2}(P_{m}\square P_{k})$$ λ 2 ( P m □ P k ) (except for the case $$P_{4}\square P_{3}$$ P 4 □ P 3 ).

Keywords: L(2; 1)-labeling; n-fold L(2; 1)-labeling; n-fold L(2; 1)-labeling number; Cartesian product; Path; Cycle (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01119-9 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:47:y:2024:i:3:d:10.1007_s10878-024-01119-9

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

DOI: 10.1007/s10878-024-01119-9

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 ().