Characterization of graphs with equal bandwidth and cyclic bandwidth

Peter C.B. Lam; W. C. Shiu; W. H. Chan

doi:10.1016/S0012-365X(00)00379-4

Characterization of graphs with equal bandwidth and cyclic bandwidth

Peter C.B. Lam^*
, W. C. Shiu
, W. H. Chan

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Journal article › peer-review

12 Citations (Scopus)

Abstract

B(G) and B_c(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 T_m,n,l with min{m,n,l}≥4 and grids P_m × P_n with m≥3 also fall in this class.

Original language	English
Pages (from-to)	283-289
Number of pages	7
Journal	Discrete Mathematics
Volume	242
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(00)00379-4
Publication status	Published - 1 Jun 2002

User-Defined Keywords

Bandwidth
Convex triangulation meshes
Cyclic bandwidth

Access to Document

10.1016/S0012-365X(00)00379-4

Cite this

@article{c77d73925eba4dafb859c2b419d723c9,

title = "Characterization of graphs with equal bandwidth and cyclic bandwidth",

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.",

keywords = "Bandwidth, Convex triangulation meshes, Cyclic bandwidth",

author = "Lam, \{Peter C.B.\} and Shiu, \{W. C.\} and Chan, \{W. H.\}",

note = "Funding Information: Partially supported by FRG, Hong Kong Baptist University; and RGC Grant, Hong Kong. ∗Corresponding author. E-mail address: [email protected] (P.C.B. Lam).",

year = "2002",

month = jun,

day = "1",

doi = "10.1016/S0012-365X(00)00379-4",

language = "English",

volume = "242",

pages = "283--289",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Characterization of graphs with equal bandwidth and cyclic bandwidth

AU - Lam, Peter C.B.

AU - Shiu, W. C.

AU - Chan, W. H.

N1 - Funding Information: Partially supported by FRG, Hong Kong Baptist University; and RGC Grant, Hong Kong. ∗Corresponding author. E-mail address: [email protected] (P.C.B. Lam).

PY - 2002/6/1

Y1 - 2002/6/1

N2 - 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.

AB - 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.

KW - Bandwidth

KW - Convex triangulation meshes

KW - Cyclic bandwidth

UR - https://www.scopus.com/pages/publications/33750809472

U2 - 10.1016/S0012-365X(00)00379-4

DO - 10.1016/S0012-365X(00)00379-4

M3 - Journal article

AN - SCOPUS:33750809472

SN - 0012-365X

VL - 242

SP - 283

EP - 289

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Characterization of graphs with equal bandwidth and cyclic bandwidth

Abstract

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this