Vol. 11, No. 1, 2018

Download this article
Download this article For screen
For printing
Recent Issues

Volume 11, 1 issue

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
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 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 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 λ-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

Diagrams of $D_1, D_2, D_3$ and table of labelings

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