Characterization of graphs with equal bandwidth and cyclic bandwidth

Peter C.B. Lam*, Wai Chee SHIU, W. H. Chan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)283-289
Number of pages7
JournalDiscrete Mathematics
Volume242
Issue number1-3
DOIs
Publication statusPublished - 1 Jun 2002

Scopus Subject Areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

User-Defined Keywords

  • Bandwidth
  • Convex triangulation meshes
  • Cyclic bandwidth

Fingerprint

Dive into the research topics of 'Characterization of graphs with equal bandwidth and cyclic bandwidth'. Together they form a unique fingerprint.

Cite this