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).
In this paper, we investigate some structural properties of resonance graphs of plane elementary bipartite graphs using Djoković – Winkler relation Θ and structural characterizations of a median ...graph. Let G be a plane elementary bipartite graph. It is known that its resonance graph Z(G) is a median graph. We first provide properties for Θ-classes of the edge set of Z(G). As a corollary, Z(G) cannot be a nontrivial Cartesian product of median graphs, which is equivalent to a result given by Zhang et al. that the distributive lattice on the set of perfect matchings of G is irreducible. We then present a decomposition structure on Z(G) with respect to a reducible face s of G. As an application, we give a necessary and sufficient condition on when Z(G) can be obtained from Z(H) by a peripheral convex expansion with respect to a reducible face s of G, where H is the subgraph of G obtained by removing all internal vertices (if exist) and edges on the common periphery of s and G. Furthermore, we show that Z(G) can be obtained from Z(H) by adding one pendent edge with the face-label s if and only if s is a forcing face of G such that both s and the infinite face of G are M-resonant for a degree-1 vertex M of Z(G). Our results generalize the peripheral convex expansion structure on Z(G) given by Klavžar et al. for the case when G is a catacondensed even ring system.
Let
G
be a graph that admits a perfect matching
M
. A forcing set
S
for a perfect matching
M
is a subset of
M
such that it is contained in no other perfect matchings of
G.
The cardinality of a ...forcing set of
M
with the smallest size is called the
forcing number
of
M
, denoted by
f
(
G, M
). The forcing spectrum of
G
is defined as: Spec(
G
) = {
f
(
G, M
)∣
M
is a perfect matching of
G
}. In this paper, by applying the
Z-
transformation graph (resonance graph) we show that for any polyomino with perfect matchings and any even polygonal chain, their forcing spectra are integral intervals. Further we obtain some sharp bounds on maximum and minimum forcing numbers of hexagonal chains with given number of kinks. Forcing spectra of two extremal chains are determined.
The concept of forcing faces of a plane bipartite graph was first introduced in Che and Chen (2008) 3 Z. Che, Z. Chen, Forcing faces in plane bipartite graphs, Discrete Mathematics 308 (2008) ...2427–2439, which is a natural generalization of the concept of forcing hexagons of a hexagonal system introduced in Che and Chen (2006) 2 Z. Che and Z. Chen, Forcing hexagons in hexagonal systems, MATCH Commun. Math. Comput. Chem. 56 (2006) 649–668. In this paper, we further extend this concept from finite faces to all faces (including the infinite face) as follows: A face s (finite or infinite) of a 2-connected plane bipartite graph G is called a forcing face if the subgraph G−V(s) obtained by removing all vertices of s together with their incident edges has exactly one perfect matching.
For a plane elementary bipartite graph G with more than two vertices, we give three necessary and sufficient conditions for G to have all faces forcing. We also give a new necessary and sufficient condition for a finite face of G to be forcing in terms of bridges in the Z-transformation graph Z(G) of G. Moreover, for the graphs G whose faces are all forcing, we obtain a characterization of forcing edges in G by using the notion of handle, from which a simple counting formula for the number of forcing edges follows.
A perfect matching of a graph is a set of independent edges that covers all vertices of the graph. A bipartite graph is elementary if and only if it is connected and each edge is contained in a ...perfect matching. The resonance graph of a plane bipartite graph
G
is a graph whose vertices are perfect matchings of
G
, and two perfect matchings are adjacent if edges contained in their union but not intersection form a cycle surrounding a finite face of
G
. It is well known that the resonance graph of a plane elementary bipartite graph is a median graph. Median graphs form an important subclass of partial cubes and have a wide range of applications. The most important structural characterization of a median graph is the Mulder’s convex expansion theorem. Fibonacci cubes used in network designs are median graphs and can be obtained from an edge by a sequence of peripheral convex expansions. Plane bipartite graphs whose resonance graphs are Fibonacci cubes were studied by Klavžar et al. first for their applications in chemistry and completely characterized by Zhang et al. later. Motivated from their work, we characterize all plane bipartite graphs whose resonance graphs can be constructed from an edge by a sequence of peripheral convex expansions.
Based on an acyclic orientation of the Z-transformation graph, a finite distributive lattice (FDL for short) M(G) is established on the set of all 1-factors of a plane (weakly) elementary bipartite ...graph G. For an FDL L, if there exists a plane bipartite graph G such that L is isomorphic to M(G), then L is called a matchable FDL. A natural question arises: Is every FDL a matchable FDL? In this paper we give a negative answer to this question. Further, we obtain a series of non-matchable FDLs by characterizing sub-structures of matchable FDLs with cut-elements.
A distributive lattice structure M(G) has been established on the set of perfect matchings of a plane bipartite graph G. We call a lattice matchable distributive lattice (simply MDL) if it is ...isomorphic to such a distributive lattice. It is natural to ask which lattices are MDLs. We show that if a plane bipartite graph G is elementary, then M(G) is irreducible. Based on this result, a decomposition theorem on MDLs is obtained: a finite distributive lattice L is an MDL if and only if each factor in any cartesian product decomposition of L is an MDL. Two types of MDLs are presented: J(m×n) and J(T), where m×n denotes the cartesian product between m-element chain and n-element chain, and T is a poset implied by any orientation of a tree.
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 Klavzar 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, Klavzar et al.'s algorithm is modified to generate this binary coding for the 1-factors of a cata-condensed benzenoid system.
Celotno besedilo
Dostopno za:
CEKLJ, DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
The Fibonacci cube
Γ
n
is a subgraph of
n
-dimensional hypercube induced by the vertices without two consecutive ones. Klavžar and Žigert Fibonacci cubes are the resonance graphs of fibonaccenes, ...Fibonacci Quart. 43 (2005) 269–276 proved that Fibonacci cubes are precisely the
Z
-transformation graphs (or resonance graphs) of zigzag hexagonal chains. In this paper, we characterize plane bipartite graphs whose
Z
-transformation graphs are exactly Fibonacci cubes. If we delete from
Γ
n
(
n
≥
3
)
all the vertices with 1 both in the first and in the last position, we obtain the Lucas cube
L
n
. We show, however, that none of the Lucas cubes are
Z
-transformation graphs, and characterize plane bipartite graphs whose
Z
-transformation graphs are
L
2
k
′
for
k
≥
2
, which is obtained from
L
2
k
by adding two vertices and joining one to
1010
…
10
and the other to
0101
…
01
.
PDF
