Cube-free resonance graphs

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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2020-09, Vol.284, p.262-268
Main Author: Che, Zhongyuan
Format: Article
Language:English
Subjects:
[formula omitted]-transformation graph
Apexes
Convex expansion
Distributive lattice
Graph theory
Lower bounds
Median graph
Perfect matching
Plane (weakly) elementary bipartite graph
Resonance
Resonance graph
Structural analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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).
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2020.03.036