|
|||||
 |
|
|
|
|
|
Labeling
crossed prisms with a condition at distance two
Matthew Beaudouin-Lafon, Serena Chen, Nathaniel Karst, Jessica Oehrlein and Denise Sakai Troxell
Vol. 11 (2018), No. 1, 67–80
DOI: 10.2140/involve.2018.11.67
|
Abstract |
|
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 -number of a graph is the minimum span of labels over all its L(2,1)-labelings. A generalized Petersen graph (GPG) of order consists of two disjoint cycles on 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 is a GPG that is isomorphic to the Cartesian product of a path on two vertices and a cycle on 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 -number of a crossed prism is 5, 6, or 7 and provide complete characterizations of crossed prisms attaining each one of these -numbers. |
Keywords
L(2,1)-labeling, L(2,1)-coloring, distance two labeling,
channel assignment, generalized Petersen graph
|
Mathematical Subject Classification 2010
Primary: 68R10, 94C15
Secondary: 05C15, 05C78
|
Supplementary material |
Milestones
Received: 9 July 2016
Revised: 18 August 2016
Accepted: 7 September 2016
Published: 17 July 2017
Communicated by Jerrold Griggs
|
Authors |
| Matthew Beaudouin-Lafon | |
| Franklin W. Olin College of
Engineering Needham, MA 02492 United States |
|
| Serena Chen | |
| Franklin W. Olin College of
Engineering Needham, MA 02492 United States |
|
| Nathaniel Karst | |
| Mathematics and Sciences
Division Babson College Babson Park, MA 02457 United States |
|
| Jessica Oehrlein | |
| Fu Foundation School of Engineering
and Applied Sciences Columbia University New York, NY 10027 United States |
|
| Denise Sakai Troxell | |
| Mathematics and Sciences
Division Babson College Babson Park, MA 02457 United States |
|
|
