Matching transformation graphs of cubic bipartite plane graphs

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


In this paper, we explore some properties of the matching transformation graph of a connected cubic bipartite plane graph G. We prove that if M is any perfect matching of G, then G has at least two disjoint M-alternating faces. This result is sharp in the sense that there are connected cubic bipartite plane graphs which do not have three disjoint M-alternating faces for some perfect matching M. We also show that the matching transformation graph of G is 2-connected.

Original languageEnglish
Pages (from-to)27-36
Number of pages10
JournalDiscrete Mathematics
Issue number1-3
Publication statusPublished - 6 Feb 2003
Externally publishedYes


  • Alternating cycles
  • Connectivity
  • Cubic graphs
  • Matching transformation graphs
  • Perfect matchings

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Matching transformation graphs of cubic bipartite plane graphs'. Together they form a unique fingerprint.

Cite this