Skip to main content
Article
Exact Lambda-Numbers of Generalized Petersen Graphs of Certain Higher-Orders and on Mobius Strips
Discrete Applied Mathematics (2012)
  • Sarah Spence Adams
  • Paul Booth
  • Harold Jaffe
  • Denise Troxell, Babson College
  • Luke Zinnen
Abstract

An L(2,1)-labeling of a graph G is an assignment f of nonnegative integers to the vertices of G such that if vertices x and y are adjacent, |f(x)−f(y)|≥2, and if x and y are at distance two, |f(x)−f(y)|≥1. The λ-number of Gis the minimum span over all L(2,1)-labelings of G. A generalized Petersen graph (GPG) of order n consists of two disjoint copies of cycles on n vertices together with a perfect matching between the two vertex sets. By presenting and applying a novel algorithm for identifying GPG-specific isomorphisms, this paper provides exact values for the λ-numbers of all GPGs of orders 9, 10, 11, and 12. For all but three GPGs of these orders, the λ-numbers are 5 or 6, improving the recently obtained upper bound of 7 for GPGs of orders 9, 10, 11, and 12. We also provide the λ-numbers of several infinite subclasses of GPGs that have useful representations on Möbius strips.

Keywords
  • L(2,
  • 1)-labeling; L(2,
  • 1)-coloring; Distance two labeling; Graph labeling; Channel assignment; Generalized Petersen graph
Disciplines
Publication Date
March, 2012
Publisher Statement

© 2012 Elsevier. This article was published in Discrete Applied Mathematics, vol. 160, iss. 4-5, pg. 436-447 and may be found here.

Citation Information
Sarah Spence Adams, Paul Booth, Harold Jaffe, Denise Troxell, et al.. "Exact Lambda-Numbers of Generalized Petersen Graphs of Certain Higher-Orders and on Mobius Strips" Discrete Applied Mathematics Vol. 160 Iss. 4-5 (2012)
Available at: http://works.bepress.com/sarah_spence_adams/24/