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 - http://www.scopus.com/inward/record.url?scp=33750809472&partnerID=8YFLogxK
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 -