Title

The minimum span of L(2,1)-Labelings of Certain Generalized Petersen Graphs

Comments

The published version is available to subscribers in Discrete Applied Mathematics, 155 (2007) 1314—1325.

doi: http://dx.doi.org/10.1016/j.dam.2006.12.001

Abstract

In the classical channel assignment problem, transmitters that are sufficiently close together are assigned transmission frequencies that differ by prescribed amounts, with the goal of minimizing the span of frequencies required. This problem can be modeled through the use of an L(2,1)-labeling, which is a function f from the vertex set of a graph G to the nonnegative integers such that |f(x) – f(y)| ≥ 2 if x and y are adjacent vertices and |f(x) – f(y)| ≥ 1 if x and y are at distance 2. The goal is to determine the l-number of G, which is defined as the minimum span over all L(2,1)-labelings of G, or equivalently, the smallest number k such that G has an L(2,1)-labeling using integers from {0, 1, …, k}. Recent work has focused on determining the l-number of generalized Petersen graphs (GPGs) of order n. This paper provides exact values for the l-numbers of GPGs of orders 5, 7, and 8, closing all remaining open cases for orders at most 8. It is also shown that there are no GPGs of orders 4, 5, 8, 11 with l-number exactly equal to the known lower bound of 5, however a construction is provided to obtain examples of GPGs with l-number 5 for all other orders. This paper also provides an upper bound for the number of distinct isomorphism classes for GPGs of any given order. Finally, the exact values for the l-number of n-stars, a subclass of the GPGs inspired by the classical Petersen graph, are also determined. These generalized stars have a useful representation on Möebius strips, which is fundamental in verifying our results.

Academic Division

Math/Science

Disciplines

Applied Mathematics

This document is currently not available here.

Share

COinS