On labeling the vertices of products of complete graphs with distance constraints

Abstract

Abstract Variations of Hale's channel assignment problem, the L ( j , k )‐labeling problem and the radio labeling problem require the assignment of integers to the vertices of a graph G subject to various distance constraints. The λ j,k ‐number of G and the radio number of G are respectively the minimum span among all L ( j , k )‐labelings, and the minimum span plus 1 of all radio labelings of G (defined in the Introduction). In this paper, we establish the λ j,k ‐number of ∏ K for pairwise relatively prime integers t 1 < t 2 < … < t q , t 1 ≥ 2. We also show the existence of an infinite class of graphs G with radio number | V ( G )| for any diameter d ( G ). © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005