Results 1 to 10 of about 47 (31)
Plane elementary bipartite graphs
Discrete Applied Mathematics, 2000 A connected graph is elementary if the union of all perfect matchings induces a connected subgraph. It is well known that a connected bipartite graph is elementary if and only if it is \(1\)-extendable, i.e., each edge is contained in a perfect matching. In this paper the authors mainly study properties of plane elementary bipartite graphs.
Heping Zhang, Fuji Zhang
exaly +6 more sources
1-factors and characterization of reducible faces of plane elementary bipartite graphs
Discussiones Mathematicae Graph Theory, 2012 As a general case of molecular graphs of benzenoid hydrocarbons, we study plane bipartite graphs with Kekule structures (1-factors). A bipartite graph G is called elementary if G is connected and every edge belongs to a 1-factor of G. Some properties of the minimal and the maximal 1-factor of a plane elementary graph are given. A peripheral face f of a
Andrej Taranenko, Aleksander Vesel
core +6 more sources
Z-transformation graphs of perfect matchings of plane bipartite graphs
Discrete Mathematics, 2004 Let G be a plane bipartite graph with at least two perfect matchings. The Z-transformation graph, ZF(G), of G with respect to a specific set F of faces is defined as a graph on the perfect matchings of G such that two perfect matchings M1 and M2 are ...
Heping Zhang, Fuji Zhang, Haiyuan Yao
exaly +3 more sources
Forcing faces in plane bipartite graphs
Discrete Mathematics, 2008 Let Ω denote the class of connected plane bipartite graphs with no pendant edges. A finite face s of a graph G∈Ω is said to be a forcing face of G if the subgraph of G obtained by deleting all vertices of s together with their incident edges has exactly ...
Zhongyuan Che, Zhibo Chen
exaly +2 more sources
Forcing faces in plane bipartite graphs (II)
Discrete Applied Mathematics, 2013 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 ...
Zhongyuan Che, Zhibo Chen
exaly +2 more sources
2-resonance of plane bipartite graphs and its applications to boron–nitrogen fullerenes
Discrete Applied Mathematics, 2010 A set H of disjoint faces of a plane bipartite graph G is a resonant pattern if G has a perfect matching M such that the boundary of each face in H is an M-alternating cycle. An elementary result was obtained [Discrete Appl. Math.
Heping Zhang
exaly +2 more sources
Z -transformation graphs of maximum matchings of plane bipartite graphs
Discrete Applied Mathematics, 2004 Let G be a plane bipartite graph. The Z-transformation graph Z(G) and its orientation Z→(G) on the maximum matchings of G are defined. If G has a perfect matching, Z(G) and Z→(G) are the usual Z-transformation graph and digraph. If G has neither isolated
Heping Zhang, Haiyuan Yao
exaly +2 more sources
Resonance graphs of plane bipartite graphs as daisy cubes
Discrete Applied MathematicsWe characterize plane bipartite graphs whose resonance graphs are daisy cubes, and therefore generalize related results on resonance graphs of benzenoid graphs, catacondensed even ring systems, as well as 2-connected outerplane bipartite graphs. Firstly,
Zhongyuan Che +2 more
exaly +3 more sources
Ars Comb., 1999 Summary: Let \(G\) be a connected plane bipartite graph. The \(Z\)-transformation graph \(Z(G)\) is a graph where the vertices are the perfect matchings of \(G\) and where two perfect matchings are joined by an edge provided their symmetric difference is the boundary of an interior face of \(G\). For a plane elementary bipartite graph \(G\) it is shown
Zhang, HP, Zhang, FJ
openaire +2 more sources
Existence of perfect matchings in a plane bipartite graph [PDF]
, 1996 summary:We give a necessary and sufficient condition for the existence of perfect matchings in a plane bipartite graph in terms of elementary edge-cut, which extends the result for the existence of perfect matchings in a hexagonal system given in the ...
Che, Zhongyuan, Kochol, Martin
core +1 more source