File(s) under permanent embargo
The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups
A k-L(2,1)-labelling of a graph G is a mapping f:V(G)→{0,1,2,…,k} such that |f(u)−f(v)|≥2 if uv∈E(G) and f(u)≠f(v) if u,v are distance two apart. The smallest positive integer k such that G admits a k-L(2,1)-labelling is called the λ-number of G. In this paper we study this quantity for cubic Cayley graphs (other than the prism graphs) on dihedral groups, which are called brick product graphs or honeycomb toroidal graphs. We prove that the λ-number of such a graph is between 5 and 7, and moreover we give a characterisation of such graphs with λ-number 5.
History
Journal
Journal of combinatorial optimizationVolume
25Issue
4Pagination
716 - 736Publisher
SpringerLocation
New York, N. Y.ISSN
1382-6905eISSN
1573-2886Language
engPublication classification
C1 Refereed article in a scholarly journalCopyright notice
2012, Springer Science+Business Media, LLCUsage metrics
Categories
No categories selectedKeywords
λ-Numberbrick productcayley graphdihedral grouphoneycomb toroidal graphhoneycomb torusL(21)-labellingScience & TechnologyTechnologyPhysical SciencesComputer Science, Interdisciplinary ApplicationsMathematics, AppliedComputer ScienceMathematicsL(2,1)-labellinglambda-NumberGENERALIZED HONEYCOMB TORUSCHANNEL ASSIGNMENT PROBLEMABELIAN-GROUPSNETWORKSDISTANCE-2COLORINGSCYCLESNUMBERL(H
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC