A maximum resonant set of polyomino graphs

DOI10.7151/DMGT.1857MaRDI QIDQ274682zbMATHOpenAlexFDO

Authors Heping Zhang, Xiangqian Zhou

Publication date 25 April 2016

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.7126

zbMATH Keywords

perfect matchingalternating setdimer problemforcing numberpolyomino graphresonant set

Mathematics Subject Classification ID

Applications of graph theory (05C90) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Abstract: A polyomino graph $H$ is a connected finite subgraph of the infinite plane grid such that each finite face is surrounded by a regular square of side length one and each edge belongs to at least one square. In this paper, we show that if $K$ is a maximum resonant set of $H$, then $H-K$ has a unique perfect matching. We further prove that the maximum forcing number of a polyomino graph is equal to its Clar number. Based on this result, we have that the maximum forcing number of a polyomino graph can be computed in polynomial time. We also show that if $K$ is a maximal alternating set of $H$, then $H-K$ has a unique perfect matching.

Recommendations

• On maximal resonance of polyomino graphs
• The maximum forcing number of a polyomino
• A minimax result for perfect matchings of a polyomino graph
• Forcing and anti-forcing polynomials of a type of polyomino graphs
• Perfect matchings of polyomino graphs

Cites work

• scientific article; zbMATH DE number 1890095 (Why is no real title available?)
• scientific article; zbMATH DE number 6127683 (Why is no real title available?)
• scientific article; zbMATH DE number 5030034 (Why is no real title available?)
• A lower bound on the number of elementary components of essentially disconnected generalized polyomino graphs
• A maximal cover of hexagonal systems
• Chessboard domination problems
• Combinatorial properties of polyominoes
• Dimers on two types of lattices on the Klein bottle
• Elementary components of essentially disconnected polyomino graphs
• Forcing matchings on square grids
• King and domino polynomials for polyomino graphs
• Matching theory
• Maximum forcing number of hexagonal systems
• On maximal resonance of polyomino graphs
• On the queen domination problem
• Perfect matchings in hexagonal systems
• Perfect matchings of polyomino graphs
• Plane elementary bipartite graphs
• Remark on the dimer problem
• Statistical Mechanics of Dimers on a Plane Lattice
• The connectivity of Z-transformation graphs of perfect matchings of hexagonal systems
• The connectivity of \(Z\)-transformation graphs of perfect matchings of polyominoes
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Unimodularity of the Clar number problem

Cited in

(8)

• Some tight bounds on the minimum and maximum forcing numbers of graphs
• On maximal resonance of polyomino graphs
• A minimax result for perfect matchings of a polyomino graph
• Forcing and anti-forcing polynomials of a type of polyomino graphs
• The maximum forcing number of a polyomino
• The polyomino graphs whose resonance graphs have a 1-degree vertex
• Relations between global forcing number and maximum anti-forcing number of a graph
• Forcing and anti-forcing polynomials of perfect matchings for some rectangle grids

This page was built for publication: A maximum resonant set of polyomino graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q274682)