TY - JOUR

T1 - Cube-free resonance graphs

AU - Che, Zhongyuan

N1 - Funding Information:
The research work is supported by the Research Development Grant (RDG) from Penn State University, Beaver Campus . The author would like to thank the referees for their helpful comments.
Publisher Copyright:
© 2020 Elsevier B.V.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/9/30

Y1 - 2020/9/30

N2 - Let G be a plane elementary bipartite graph with more than two vertices. Then its resonance graph Z(G) is a median graph and the set M(G) of all perfect matchings of G with a specific partial order is a finite distributive lattice. In this paper, we prove that Z(G) is cube-free if and only if it can be obtained from an edge by a sequence of convex path expansions with respect to a reducible face decomposition of G. As a corollary, a structure characterization is provided for G whose Z(G) is cube-free. Furthermore, Z(G) is cube-free if and only if the Clar number of G is at most two, and sharp lower bounds on the number of perfect matchings of G can be expressed by the number of finite faces of G and the number of Clar formulas of G. It is known that a cube-free median graph is not necessarily planar. Using the lattice structure on M(G), we show that Z(G) is cube-free if and only if Z(G) is planar if and only if M(G) is an irreducible sublattice of m×n. We raise a question on how to characterize irreducible sublattices of m×n that are M(G).

AB - Let G be a plane elementary bipartite graph with more than two vertices. Then its resonance graph Z(G) is a median graph and the set M(G) of all perfect matchings of G with a specific partial order is a finite distributive lattice. In this paper, we prove that Z(G) is cube-free if and only if it can be obtained from an edge by a sequence of convex path expansions with respect to a reducible face decomposition of G. As a corollary, a structure characterization is provided for G whose Z(G) is cube-free. Furthermore, Z(G) is cube-free if and only if the Clar number of G is at most two, and sharp lower bounds on the number of perfect matchings of G can be expressed by the number of finite faces of G and the number of Clar formulas of G. It is known that a cube-free median graph is not necessarily planar. Using the lattice structure on M(G), we show that Z(G) is cube-free if and only if Z(G) is planar if and only if M(G) is an irreducible sublattice of m×n. We raise a question on how to characterize irreducible sublattices of m×n that are M(G).

UR - http://www.scopus.com/inward/record.url?scp=85082736738&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85082736738&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2020.03.036

DO - 10.1016/j.dam.2020.03.036

M3 - Article

AN - SCOPUS:85082736738

SN - 0166-218X

VL - 284

SP - 262

EP - 268

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -