Cyclic bandwidth with an edge added

B c ( G ) denotes the cyclic bandwidth of graph G. In this paper, we obtain the maximum cyclic bandwidth of graphs of order p with adding an edge e ∈ E [ G ¯ ] as follows: B c ( G + e ) = 2 B c ( G ) if B c ( G ) ⩽ p 8 , 1 3 p 2 + 2 B c ( G ) if B c ( G ) > p 8 . We also show that this bound is s...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2008, Vol.156 (1), p.131-137
Main Authors: Chan, W.H., Lam, Peter C.B., Shiu, W.C.
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Bandwidth
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Cyclic bandwidth
Exact sciences and technology
Graph theory
Information retrieval. Graph
Mathematics
Sciences and techniques of general use
Theoretical computing
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:B c ( G ) denotes the cyclic bandwidth of graph G. In this paper, we obtain the maximum cyclic bandwidth of graphs of order p with adding an edge e ∈ E [ G ¯ ] as follows: B c ( G + e ) = 2 B c ( G ) if B c ( G ) ⩽ p 8 , 1 3 p 2 + 2 B c ( G ) if B c ( G ) > p 8 . We also show that this bound is sharp.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2007.09.011