\(L(2,1)\) -labeling for brick product graphs

详细信息    查看全文

• 作者：Zehui Shao ; Jin Xu ; Roger K. Yeh
• 关键词：L(2 ; 1) ; labeling ; Brick product graph ; Graph labeling ; Frequency assignment problem
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：31
• 期：2
• 页码：447-462
• 全文大小：448 KB
• 参考文献：Bodlaender HL, Kloks T, Tan RB, van Leeuwen J (2004) The \(L\) (2, 1)-labeling problem on graphs. Comput J 47:193–204
  Calamoneri T (2011) The \(L(h, k)\) -labeling problem: a updated aurvey and annotated bibliography. Comput J 54:1344–1371
  Fiala J, Golovach PA, Kratochvíl JK (2005) Distance constrained labelings of graphs of bounded treewidth. In Proceedings of the 32th ICALP 9:360–372
  Griggs JR, Yeh RK (1992) Labelling graphs with a condition at distance 2. SIAM J Discret Math 308:586–595MathSciNet CrossRef
  Hale WK (1980) Frequency assignment: theory and applications. Proc IEEE 68:1497–1514CrossRef
  Jha PK (2001) Optimal \(L\) (2, 1)-labeling of strong products of cycles. IEEE Trans Circ Sys I Fund Theory Appl 48:498–500
  Klavžar S, Vesel A (2003) Computing graph invariants on rotagraphs using dynamic algorithm approach: the case of (2,1)-colorings and independence numbers. Discret Appl Math 129:449–460CrossRef MATH
  Korz̆e D, Vesel A (2005) \(L\) (2, 1)-labeling of strong products of cycles. Inf Process Lett 94:183–190
  Kratochvíl J, Kratsch D, Liedloff M (2007) Exact algorithms for \(L\) (2, 1)-labeling of graphs. MFCS 2007. LNCS 4708:513–524
  Li X, Mak-Hau V, Zhou S (2013) The \(L(2, 1)\) -labelling problem for cubic cayley graphs on dihedral groups. J Comb Optim 25:716–736
  Schwarz C, Troxell DS (2006) \(L(2, 1)\) -labelings of products of two cycles. Disc Appl Math 154:1522–1540
  Whittlesey MA, Georges JP, Mauro DW (1995) On the \(\lambda \) number of \(q_n\) and related graphs. SIAM J Discret Math 8:499–506MathSciNet CrossRef MATH
  Yeh RK (2006) A survey on labeling graphs with a condition at distance two. Discret Math 306:1217–1231CrossRef MATH
  
• 作者单位：Zehui Shao (1) (2)
  Jin Xu (3)
  Roger K. Yeh (4)
  
  1. School of Information Science and Technology, Chengdu University, Chengdu, 610106, China
  2. Key Laboratory of Pattern Recognition and Intelligent Information Processing, Institutions of Higher Education of Sichuan Province, Chengdu, China
  3. School of Electronic Engineering and Computer Science, Peking University, Beijing, 100871, China
  4. Department of Applied Mathematics, Feng Chia University, Taichung, Taiwan
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

Let \(G=(V, E)\) be a graph. Denote \(d_G(u, v)\) the distance between two vertices \(u\) and \(v\) in \(G\). An \(L(2, 1)\)-labeling of \(G\) is a function \(f: V \rightarrow \{0,1,\cdots \}\) such that for any two vertices \(u\) and \(v\), \(|f(u)-f(v)| \ge 2\) if \(d_G(u, v) = 1\) and \(|f(u)-f(v)| \ge 1\) if \(d_G(u, v) = 2\). The span of \(f\) is the difference between the largest and the smallest number in \(f(V)\). The \(\lambda \)-number of \(G\), denoted \(\lambda (G)\), is the minimum span over all \(L(2,1 )\)-labelings of \(G\). In this article, we confirm Conjecture 6.1 stated in X. Li et al. (J Comb Optim 25:716–736, 2013) in the case when (i) \(\ell \) is even, or (ii) \(\ell \ge 5\) is odd and \(0 \le r \le 8\). Keywords L(2, 1)-labeling Brick product graph Graph labeling Frequency assignment problem