Abstract
B(G) and Bc(G) denote the bandwidth and cyclic bandwidth of graph G, respectively. In this paper, we shall give a characterization of graphs with equal bandwidth and cyclic bandwidth. Those graphs include any plane graph G with B(G) <p/m, where p and m are the number of vertices and the maximum degree of bounded faces of G, respectively. Hence convex triangulation meshes Tm,n,l with min{m,n,l}⩾4 and grids Pm×Pn with m⩾3 also fall in this class. Copyright © 2002 Elsevier Science B.V. All rights reserved.
Original language | English |
---|---|
Pages (from-to) | 283-289 |
Journal | Discrete Mathematics |
Volume | 242 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - Jan 2002 |
Citation
Lam, P. C. B., Shiu, W. C., & Chan, W. H. (2002). Characterization of graphs with equal bandwidth and cyclic bandwidth. Discrete Mathematics, 242(1), 283-289. doi: 10.1016/S0012-365X(00)00379-4Keywords
- Bandwidth
- Cyclic bandwidth
- Convex triangulation meshes