The \(L(2,1)\)-labelling problem for cubic Cayley graphs on dihedral groups. (English) Zbl 1273.90227
Summary: A \(k-L(2,1)\)-labelling of a graph \(G\) is a mapping \(f:V(G)\rightarrow \{0,1,2,\dots,k\}\) such that \(| f(u)-f(v)|\geq 2\) if \(uv\in E(G)\) and \(f(u)\neq f(v)\) if \(u,v\) are distance two apart. The smallest positive integer \(k\) such that \(G\) admits a \(k-L(2,1)\)-labelling is called the \(\lambda\)-number of \(G\). In this paper, we study this quantity for cubic Cayley graphs (other than the prism graphs) on dihedral groups, which are called brick product graphs or honeycomb toroidal graphs. We prove that the \(\lambda\)-number of such a graph is between 5 and 7, and moreover, we give a characterization of such graphs with \(\lambda\)-number 5.
MSC:
| 90C35 | Programming involving graphs or networks |
Keywords:
\(L(2,1)\)-labelling; \(\lambda\)-number; brick product; honeycomb toroidal graph; honeycomb torus; Cayley graph; dihedral groupReferences:
| [1] | Alspach B, Chen CC, Mcavanney K (1996) On a class of Hamiltonian laceable 3-regular graphs. Discrete Math 151:19-38 · Zbl 0855.05078 · doi:10.1016/0012-365X(94)00077-V |
| [2] | Alspach B, Dean M (2009) Honeycomb toroidal graphs are Cayley graphs. Inf Process Lett 109:705-708 · Zbl 1197.05070 · doi:10.1016/j.ipl.2009.03.009 |
| [3] | Alspach B, Zhang CQ (1989) Hamilton cycles in cubic graphs on dihedral groups. Ars Comb 28:101-108 · Zbl 0722.05047 |
| [4] | Bahls P (2011) Channel assignment on Cayley graphs. J Graph Theory 67(3):169-177 · Zbl 1222.05228 · doi:10.1002/jgt.20523 |
| [5] | Bodlaender HL, Kloks T, Tan RB, van Leeuwen J (2004) Approximations for λ-coloring of graphs. Comput J 47:193-204 · Zbl 1039.68090 · doi:10.1093/comjnl/47.2.193 |
| [6] | Calamoneri T, Petreschi R (2004) L(h,1)-labeling subclasses of planar graphs. J Parallel Distrib Comput 64(3):414-426. · Zbl 1084.68089 · doi:10.1016/j.jpdc.2003.11.005 |
| [7] | Calamoneri T (2011) The L(h,k)-labelling problem: an updated survey and annotated bibliography. Comput J 54:1344-1371 · doi:10.1093/comjnl/bxr037 |
| [8] | Calamoneri T, Caminiti S, Petreschi R (2008) A general approach to L(h,k)-label interconnection networks. J Comput Sci Technol 23(4):652-659 · doi:10.1007/s11390-008-9161-8 |
| [9] | Chang GJ, Kuo D (1996) The L(2,1)-labelling problem on graphs. SIAM J Discrete Math 9:309-316 · Zbl 0860.05064 · doi:10.1137/S0895480193245339 |
| [10] | Chang GJ, Lu CH, Zhou S (2009) Distance-two labellings of Hamming graphs. Discrete Appl Math 157:1896-1904 · Zbl 1213.05231 · doi:10.1016/j.dam.2009.01.001 |
| [11] | Chang GJ, Lu CH, Zhou S (2007) No-hole 2-distant colorings for Cayley graphs on finitely generated Abelian groups. Discrete Math 307:1808-1817 · Zbl 1117.05039 · doi:10.1016/j.disc.2006.09.030 |
| [12] | Cho H, Hsu L (2003) Generalized honeycomb torus. Inf Process Lett 86:185-190 · Zbl 1162.68739 · doi:10.1016/S0020-0190(02)00507-0 |
| [13] | Coxeter HSM (1950) Self dual configurations and regular graphs. Bull Am Math Soc 56:413-455 · Zbl 0040.22803 · doi:10.1090/S0002-9904-1950-09407-5 |
| [14] | Georges JP, Mauro DW (2002) On generalized Petersen graphs labelled with a condition at distance two. Discrete Math 259:311-318 · Zbl 1008.05129 · doi:10.1016/S0012-365X(02)00302-3 |
| [15] | Goncalves D (2008) On the L(p,1)-labelling of graphs. Discrete Math 308:1405-1414 · Zbl 1135.05065 · doi:10.1016/j.disc.2007.07.075 |
| [16] | Griggs JR, Yeh RK (1992) Labelling graphs with a condition at distance 2. SIAM J Discrete Math 5:586-595 · Zbl 0767.05080 · doi:10.1137/0405048 |
| [17] | Hale WK (1980) Frequency assignment: Theory and applications. Proc IEEE 68:1497-1514 · doi:10.1109/PROC.1980.11899 |
| [18] | Havet F, Reed B, Sereni J-S (2012) Griggs and Yeh’s conjecture and L(p,1)-labelings. SIAM J Discrete Math 26:145-168 · Zbl 1245.05110 · doi:10.1137/090763998 |
| [19] | Jha PK, Narayanan A, Sood P, Sundaram K, Sunder V (2000) On L(2;1)-labeling of the Cartesian product of a cycle and a path. Ars Comb 55:81-89 · Zbl 0994.05135 |
| [20] | Kang J-H (2008) L(2,1)-labelling of Hamiltonian graphs with maximum degree 3. SIAM J Discrete Math 22:213-230 · Zbl 1159.05045 · doi:10.1137/050632609 |
| [21] | Král’ D, Škrekovski R (2003) A theorem about the channel assignment problem. SIAM J Discrete Math 16:426-437 · Zbl 1029.05053 · doi:10.1137/S0895480101399449 |
| [22] | Kuo D, Yan J-H (2004) On L(2,1)-labellings of Cartesian products of paths and cycles. Discrete Math 283:137-144 · Zbl 1043.05104 · doi:10.1016/j.disc.2003.11.009 |
| [23] | Li X, Mak-Hau V, Zhou S (2012) Distance-two labellings for chordal rings of degree three. In preparation · Zbl 1084.68089 |
| [24] | Li X, Zhou S (2012) Labeling outerplanar graphs with maximum degree three. Preprint · Zbl 1364.05058 |
| [25] | Liu DD, Zhu X (2005) Circular distance two labelling and the λ-number for outerplanar graphs. SIAM J Discrete Math 19:281-291 · Zbl 1090.05027 · doi:10.1137/S0895480102414296 |
| [26] | Marušič D, Pisanski T (2000) Symmetries of hexagonal molecular graphs on the torus. Croat Chem 73:969-981 |
| [27] | Molloy M, Salavatipour MR (2005) A bound on the chromatic number of the square of a planar graph. J Comb Theory, Ser B 94:189-213 · Zbl 1071.05036 · doi:10.1016/j.jctb.2004.12.005 |
| [28] | Sakai D (1994) Labelling chordal graphs: distance two condition. SIAM J Discrete Math 7:133-140 · Zbl 0794.05118 · doi:10.1137/S0895480191223178 |
| [29] | Stojmenovic I (1997) Honeycomb networks: topological properties and communication algorithms. IEEE Trans Parallel Distrib Syst 8:1036-1042 · doi:10.1109/71.629486 |
| [30] | Xiao W, Parhami B (2007) Further mathematical properties of Cayley digraphs applied to hexagonal and honeycomb meshes. Discrete Appl Math 155:1752-1760 · Zbl 1127.68072 · doi:10.1016/j.dam.2007.04.002 |
| [31] | Yang X, Evans DJ, Lai H, Megson GM (2004) Generalized honeycomb torus is hamiltonian. Inf Process Lett 92:31-37 · Zbl 1173.68426 · doi:10.1016/j.ipl.2004.05.017 |
| [32] | Zhou S (2004) A channel assignment problem for optical networks modelled by Cayley graphs. Theor Comput Sci 310:501-511 · Zbl 1071.68085 · doi:10.1016/S0304-3975(03)00394-3 |
| [33] | Zhou S (2006) Labelling Cayley graphs on Abelian groups. SIAM J Discrete Math 19:985-1003 · Zbl 1103.05080 · doi:10.1137/S0895480102404458 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
