## 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 language | English |
---|---|

Pages (from-to) | 127-137 |

Number of pages | 11 |

Journal | MATCH Communications in Mathematical and in Computer Chemistry |

Volume | 49 |

Publication status | Published - Sept 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