Plane elementary bipartite graphs
From MaRDI portal
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. Firstly, they show that a plane bipartite graph \(G\) is elementary if and only if the boundary of each face is an alternating cycle with respect to some perfect matching of \(G\). Secondly, the concept of the so-called \(Z\)-transformation graph \(Z(G)\) of a hexagonal system \(G\) (whose vertices represent the perfect matchings of \(G\)) is extended to an arbitrary plane bipartite graph \(G\), and some results analogous to those for hexagonal systems are presented. Thirdly, they obtain the reducible face decomposition for plane elementary bipartite graphs, where a peripheral face \(f\) is called reducible if the removal of the internal vertices and edges of the path that is the intersection of \(f\) and the exterior face results in a plane elementary bipartite graph. Using the well-known bipartite ear decomposition, it follows that a plane bipartite graph different from \(K_2\) is elementary if and only if it has a reducible face decomposition. Furthermore, sharp upper and lower bounds for the number of reducible faces are derived.
Recommendations
- 1-factors and characterization of reducible faces of plane elementary bipartite graphs
- Total Z-transformation graphs of perfect matching of plane bipartite graphs
- scientific article; zbMATH DE number 1792672
- Z-transformation graphs of perfect matchings of plane bipartite graphs
- Perfect matchings and ears in elementary bipartite graphs
Cites work
- \(k\)-cycle resonant graphs
- Extending matchings in graphs: A survey
- Generalized hexagonal systems with each hexagon being resonant
- Graph theory with applications
- Hexagonal systems with forcing edges
- scientific article; zbMATH DE number 3882430 (Why is no real title available?)
- scientific article; zbMATH DE number 168169 (Why is no real title available?)
- scientific article; zbMATH DE number 168173 (Why is no real title available?)
- scientific article; zbMATH DE number 1792672 (Why is no real title available?)
- scientific article; zbMATH DE number 4118405 (Why is no real title available?)
- scientific article; zbMATH DE number 4189780 (Why is no real title available?)
- Matching theory
- On minimal elementary bipartite graphs
- On n-extendable graphs
- Perfect matchings in hexagonal systems
- Perfect matchings of polyomino graphs
- The connectivity of \(Z\)-transformation graphs of perfect matchings of polyominoes
- The connectivity of Z-transformation graphs of perfect matchings of hexagonal systems
- The rotation graphs of perfect matchings of plane bipartite graphs
- The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
- When each hexagon of a hexagonal system covers it
- Z-transformation graphs of perfect matchings of hexagonal systems
Cited in
(90)- Fibonacci-like cubes as \(Z\)-transformation graphs
- The graph of perfect matching polytope and an extreme problem
- Perfect matchings of polyomino graphs
- Cell rotation graphs of strongly connected orientations of plane graphs with an application
- \(Z\)-transformation graphs of maximum matchings of plane bipartite graphs
- Z-transformation graphs of perfect matchings of plane bipartite graphs
- Structural properties of resonance graphs of plane elementary bipartite graphs
- Anti-forcing spectrum of any cata-condensed hexagonal system is continuous
- On the perfect matching graph defined by a set of cycles
- A characterization of the resonance graph of an outerplane bipartite graph
- Distance between \(\alpha\)-orientations of plane graphs by facial cycle reversals
- The Z-transformation graph for an outerplane bipartite graph has a Hamilton path.
- The connectivity of \(Z\)-transformation graphs of perfect matchings of polyominoes
- On maximal resonance of polyomino graphs
- Structure of Fibonacci cubes: a survey
- Plane elementary bipartite graphs with forcing or anti-forcing edges
- Continuous forcing spectra of even polygonal chains
- Complete forcing numbers of hexagonal systems
- Complete forcing numbers of hexagonal systems. II
- Some novel minimax results for perfect matchings of hexagonal systems
- Determining which Fibonacci (\(p,r\))-cubes can be \(Z\)-transformation graphs
- Resonance graphs of catacondensed even ring systems
- The \(B\)-model connection and mirror symmetry for Grassmannians
- Complete forcing numbers of catacondensed hexagonal systems
- Regular coronoids and 4-tilings
- Forcing faces in plane bipartite graphs
- Fibonacci dimension of the resonance graphs of catacondensed benzenoid graphs
- On plane bipartite graphs without fixed edges
- \(k\)-resonance in toroidal polyhexes
- Decomposition theorem on matchable distributive lattices
- Peripheral convex expansions of resonance graphs
- Forcing and anti-forcing polynomials of a type of polyomino graphs
- Flips on homologous orientations of surface graphs with prescribed forbidden facial cycles
- A maximum resonant set of polyomino graphs
- A minimax result for perfect matchings of a polyomino graph
- Graphs whose characteristic and permanental polynomials have coefficients of the same magnitude
- Dehn coloring and the dimer model for knots
- Existence of perfect matchings in a plane bipartite graph
- Uniquely forced perfect matching and unique 3-edge-coloring
- Complete forcing numbers of primitive coronoids
- Plane subgraphs in geometric complement of 2-factor and complete bipartite geometric graph
- Regular Coronoids and Ear Decompositions of Plane Elementary Bipartite Graphs
- A characterization of 1-cycle resonant graphs among bipartite 2-connected plane graphs
- Hexagonal resonance of (3,6)-fullerenes
- Computing the permanental polynomials of bipartite graphs by Pfaffian orientation
- 1-factors and characterization of reducible faces of plane elementary bipartite graphs
- Kauffman's clock lattice as a graph of perfect matchings: a formula for its height
- Non-matchable distributive lattices
- scientific article; zbMATH DE number 2124506 (Why is no real title available?)
- Anti-forcing spectra of perfect matchings of graphs
- Pattern formation by oblivious asynchronous mobile robots
- Extremal anti-forcing numbers of perfect matchings of graphs
- Regular generalized polyomino graphs
- Complete forcing numbers of graphs
- Anti-forcing numbers of perfect matchings of graphs
- Maximizing the minimum and maximum forcing numbers of perfect matchings of graphs
- 2-resonance of plane bipartite graphs and its applications to boron-nitrogen fullerenes
- Maximal resonance of cubic bipartite polyhedral graphs
- Binary Coding of Resonance Graphs of Catacondensed Polyhexes
- Resonance Graphs and a Binary Coding of Perfect Matchings of Outerplane Bipartite Graphs
- Resonance graphs on perfect matchings of graphs on surfaces
- Outerplane bipartite graphs with isomorphic resonance graphs
- On forcing matching number of boron-nitrogen fullerene graphs
- The polyomino graphs whose resonance graphs have a 1-degree vertex
- A note on the number of perfect matchings of bipartite graphs
- The structural properties of \(\{(2, 3), 6 \}\)-spheres
- Resonant patterns in boron-nitrogen fullerenes
- Components of flip graphs of domino tilings in quadriculated cylinder and torus
- Some novel minimax results for perfect matchings of polyomino graphs
- Relations between polynomials based on perfect matchings and independent sets of CERS
- A decomposition structure of resonance graphs that are daisy cubes
- Forcing, anti-forcing, global forcing and complete forcing on perfect matchings of graphs -- a survey
- Components of domino tilings under flips in quadriculated tori
- Resonance graphs of plane bipartite graphs as daisy cubes
- Maximally resonant polygonal systems
- The global forcing number of the parallelogram polyhex
- Isometric embeddings of resonance graphs as finite distributive lattices
- Resonance graphs that are daisy cubes: from hypercubes to independent sets via resonant sets
- The resonance graphs of coronoid systems and nanotubes
- Cube-free resonance graphs
- The anti-Kekulé number of graphs
- A min-max result on outerplane bipartite graphs
- A complete characterization for k-resonant Klein-bottle polyhexes
- The forcing number of toroidal polyhexes
- \(k\)-resonant toroidal polyhexes
- Characterization of reducible hexagons and fast decomposition of elementary benzenoid graphs
- Relations between Clar structures, Clar covers, and the sextet-rotation tree of a hexagonal system
- Forcing matching numbers of fullerene graphs
- Direct sum of distributive lattices on the perfect matchings of a plane bipartite graph
- Bipartite matching extendable graphs
This page was built for publication: Plane elementary bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1582086)
