Premium
On labeling the vertices of products of complete graphs with distance constraints
Author(s) -
Erwin D.J.,
Georges J.P.,
Mauro D.W.
Publication year - 2005
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.10080
Subject(s) - combinatorics , mathematics , pairwise comparison , graph , class (philosophy) , discrete mathematics , coprime integers , hypergraph , computer science , statistics , artificial intelligence
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 ∏ i =1 qK t ifor 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