A maximum resonant set of polyomino graphs

DOI10.7151/DMGT.1857zbMATH Open1334.05122arXiv1411.7126OpenAlexW1553877994MaRDI QIDQ274682FDOQ274682

Heping Zhang, Xiangqian Zhou

Publication date: 25 April 2016

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

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.

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

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

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)

Cites Work

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

Cited In (5)

• A minimax result for perfect matchings of a polyomino graph
• Forcing and anti-forcing polynomials of a type of polyomino graphs
• Relations between global forcing number and maximum anti-forcing number of a graph
• Some tight bounds on the minimum and maximum forcing numbers of graphs
• 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)