Labeling crossed prisms with a condition at distance two. (English) Zbl 1369.05064

Beaudouin-Lafon, Matthew; Chen, Serena; Karst, Nathaniel; Oehrlein, Jessica; Sakai Troxell, Denise

Involve 11, No. 1, 67-80 (2018).

Summary: An \(L(2,1)\)-labeling of a graph is an assignment of nonnegative integers to its vertices such that adjacent vertices are assigned labels at least two apart, and vertices at distance two are assigned labels at least one apart. The \(\lambda\)-number of a graph is the minimum span of labels over all its \(L(2,1)\)-labelings. A generalized Petersen graph (GPG) of order \(n\) consists of two disjoint cycles on \(n\) vertices, called the inner and outer cycles, respectively, together with a perfect matching in which each matching edge connects a vertex in the inner cycle to a vertex in the outer cycle. A prism of order \(n \geq 3\) is a GPG that is isomorphic to the Cartesian product of a path on two vertices and a cycle on \(n\) vertices. A crossed prism is a GPG obtained from a prism by crossing two of its matching edges; that is, swapping the two inner cycle vertices on these edges. We show that the \(\lambda\)-number of a crossed prism is 5, 6, or 7 and provide complete characterizations of crossed prisms attaining each one of these \(\lambda\)-numbers.

MSC:

05C15	Coloring of graphs and hypergraphs
05C78	Graph labelling (graceful graphs, bandwidth, etc.)
05C12	Distance in graphs
05C76	Graph operations (line graphs, products, etc.)

Keywords:

\(L(2,1)\)-labeling; \(L(2,1)\)-coloring; distance two labeling; channel assignment; generalized Petersen graph

References:

[1]	10.1109/TCSI.2005.862184 · Zbl 1374.05187 · doi:10.1109/TCSI.2005.862184
[2]	10.1016/j.dam.2006.12.001 · Zbl 1120.05074 · doi:10.1016/j.dam.2006.12.001
[3]	10.1016/j.dam.2011.10.021 · Zbl 1239.05160 · doi:10.1016/j.dam.2011.10.021
[4]	10.1093/comjnl/bxr037 · doi:10.1093/comjnl/bxr037
[5]	10.2140/involve.2015.8.541 · Zbl 1316.05106 · doi:10.2140/involve.2015.8.541
[6]	10.1016/S0012-365X(02)00302-3 · Zbl 1008.05129 · doi:10.1016/S0012-365X(02)00302-3
[7]	10.1137/S0895480101391247 · Zbl 1041.05067 · doi:10.1137/S0895480101391247
[8]	10.1137/0405048 · Zbl 0767.05080 · doi:10.1137/0405048
[9]	10.1109/PROC.1980.11899 · doi:10.1109/PROC.1980.11899
[10]	10.1137/090763998 · Zbl 1245.05110 · doi:10.1137/090763998
[11]	10.1007/s10878-011-9380-8 · Zbl 1261.90075 · doi:10.1007/s10878-011-9380-8
[12]	; Jha, Ars Combin., 55, 81 (2000)
[13]	10.1016/S0166-218X(02)00597-8 · Zbl 1025.05059 · doi:10.1016/S0166-218X(02)00597-8
[14]	10.1016/j.disc.2003.11.009 · Zbl 1043.05104 · doi:10.1016/j.disc.2003.11.009