Resonance graphs and a binary coding for the 1-factors of benzenoid systems

Heping Zhang*, Peter Che Bor Lam, Wai Chee SHIU

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

28 Citations (Scopus)

Abstract

Applying the recently obtained distributive lattice structure on the set of 1-factors, we show that the resonance graphs of any benzenoid systems G, as well as of general plane (weakly) elementary bipartite graphs, are median graphs and thus extend greatly KlavŽar et al.'s result. The n-dimensional vectors of nonnegative integers as a labelling for the 1-factors of G with n inner faces are described. The labelling preserves the partial ordering of the above-mentioned lattice and can be transformed into a binary coding for the 1-factors. A simple criterion for such a labelling being binary is given. In particular, KlavŽar et al.'s algorithm is modified to generate this binary coding for the 1-factors of a cata-condensed benzenoid system.

Original languageEnglish
Pages (from-to)971-984
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Volume22
Issue number3
DOIs
Publication statusPublished - 2008

Scopus Subject Areas

  • Mathematics(all)

User-Defined Keywords

  • 1-factor
  • Benzenoid system
  • Binary coding
  • Distributive lattice
  • Median graph
  • Resonance graph
  • Z-transformation graph

Fingerprint

Dive into the research topics of 'Resonance graphs and a binary coding for the 1-factors of benzenoid systems'. Together they form a unique fingerprint.

Cite this