Elementary Blocks of Plane Bipartite Graphs

Peter C.B. Lam*, Wai Chee SHIU, Heping Zhang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)127-137
Number of pages11
JournalMatch
Issue number49
Publication statusPublished - Sep 2003

Scopus Subject Areas

  • Chemistry(all)
  • Computer Science Applications
  • Computational Theory and Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Alternating path
  • Elementary component
  • Noncrossing partition
  • Perfect matching
  • Plane bipartite graph

Fingerprint

Dive into the research topics of 'Elementary Blocks of Plane Bipartite Graphs'. Together they form a unique fingerprint.

Cite this