TY - JOUR
T1 - Elementary Blocks of Plane Bipartite Graphs
AU - Lam, Peter C. B.
AU - Shiu, Wai Chee
AU - Zhang, Heping
N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2003/9
Y1 - 2003/9
N2 - Let G be a 2-connected plane bipartite graph with perfect matchings, with more than one cycle and with minimum degree of interior vertices larger than 2. An edge of G is called non-fixed if it belongs to some, but not to all, perfect matchings of G. Every component of the subgraph formed by all non-fixed edges of G is called an elementary component. If each interior face of an elementary component is a face of G, then this elementary component is called an elementary block. It is known that each elementary component of a hexagonal system is an elementary block. In this paper, the concept of maximal fixed alternating path, is introduced and will be used conveniently to simplify the discussion of elementary components. In particular, we give a sharp lower bound for the number of elementary blocks of G whenever G has a cycle as its elementary block. As an application, a stronger result on the number of normal components of hexagonal systems is obtained.
AB - Let G be a 2-connected plane bipartite graph with perfect matchings, with more than one cycle and with minimum degree of interior vertices larger than 2. An edge of G is called non-fixed if it belongs to some, but not to all, perfect matchings of G. Every component of the subgraph formed by all non-fixed edges of G is called an elementary component. If each interior face of an elementary component is a face of G, then this elementary component is called an elementary block. It is known that each elementary component of a hexagonal system is an elementary block. In this paper, the concept of maximal fixed alternating path, is introduced and will be used conveniently to simplify the discussion of elementary components. In particular, we give a sharp lower bound for the number of elementary blocks of G whenever G has a cycle as its elementary block. As an application, a stronger result on the number of normal components of hexagonal systems is obtained.
KW - Alternating path
KW - Elementary component
KW - Noncrossing partition
KW - Perfect matching
KW - Plane bipartite graph
UR - https://match.pmf.kg.ac.rs/content49.htm
UR - http://www.scopus.com/inward/record.url?scp=0344629310&partnerID=8YFLogxK
M3 - Journal article
AN - SCOPUS:0344629310
SN - 0340-6253
VL - 49
SP - 127
EP - 137
JO - MATCH Communications in Mathematical and in Computer Chemistry
JF - MATCH Communications in Mathematical and in Computer Chemistry
ER -