Antibandwidth and Cyclic Antibandwidth of Hamming Graphs

The antibandwidth problem is to label vertices of graph G ( V , E ) bijectively by integers 0 , 1 , … , | V | − 1 in such a way that the minimal difference of labels of adjacent vertices is maximised. In this paper we study the antibandwidth of Hamming graphs. We provide labeling algorithms and tigh...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in discrete mathematics 2009-08, Vol.34, p.295-300
Main Authors: Dobrev, Stefan, Královič, Rastislav, Pardubská, Dana, Török, L'ubomír, Vrt'o, Imrich
Format: Article
Language:English
Subjects:
antibandwidth
Hamming graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The antibandwidth problem is to label vertices of graph G ( V , E ) bijectively by integers 0 , 1 , … , | V | − 1 in such a way that the minimal difference of labels of adjacent vertices is maximised. In this paper we study the antibandwidth of Hamming graphs. We provide labeling algorithms and tight upper bounds for general Hamming graphs ∏ k = 1 d K n k . We have exact values for special choices of n i 's and equality between antibandwidth and cyclic antibandwidth values.
ISSN:1571-0653
1571-0653
DOI:10.1016/j.endm.2009.07.048