A maximum resonant set of polyomino graphs
Copyright policy )A maximum resonant set of polyomino graphs
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.
13 pages, 6 figures
- Lanzhou University China (People's Republic of)
dimer problem, alternating set, Applications of graph theory, perfect matching, forcing number, Molecular structure (graph-theoretic methods, methods of differential topology, etc.), resonant set, polyomino graph, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), QA1-939, FOS: Mathematics, 05C70, 05C90, 92E10, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics
dimer problem, alternating set, Applications of graph theory, perfect matching, forcing number, Molecular structure (graph-theoretic methods, methods of differential topology, etc.), resonant set, polyomino graph, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), QA1-939, FOS: Mathematics, 05C70, 05C90, 92E10, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).9 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!