错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Fei-Huang Chang,
  • Ma-Lian Chia,
  • Shih-Ang Jiang,
  • David Kuo,
  • Jing-Ho Yan

摘要

For two sets of nonnegative integers A and B, the distance between these two sets, denoted by d(AB), 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(pq)-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(pq)-labeling f of G is an n-fold L(pq)-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(pq)-labeling is called the n -fold L(pq)-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 nm 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 ).