Geodesic
A Maximum Resonant Set of Polyomino Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 323-337.

Voir la notice de l'article provenant de la source Library of Science

A polyomino graph P 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. A dimer covering of P corresponds to a perfect matching. Different dimer coverings can interact via an alternating cycle (or square) with respect to them. A set of disjoint squares of P is a resonant set if P has a perfect matching M so that each one of those squares is M-alternating. In this paper, we show that if K is a maximum resonant set of P, then P − K has a unique perfect matching. We further prove that the maximum forcing number of a polyomino graph is equal to the cardinality of a maximum resonant set. This confirms a conjecture of Xu et al. [26]. We also show that if K is a maximal alternating set of P, then P − K has a unique perfect matching.
Keywords: polyomino graph, dimer problem, perfect matching, resonant set, forcing number, alternating set 
@article{DMGT_2016_36_2_a5,
     author = {Zhang, Heping and Zhou, Xiangqian},
     title = {A {Maximum} {Resonant} {Set} of {Polyomino} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {323--337},
     publisher = {mathdoc},
     volume = {36},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a5/}
}
TY  - JOUR
AU  - Zhang, Heping
AU  - Zhou, Xiangqian
TI  - A Maximum Resonant Set of Polyomino Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 323
EP  - 337
VL  - 36
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a5/
LA  - en
ID  - DMGT_2016_36_2_a5
ER  - 
%0 Journal Article
%A Zhang, Heping
%A Zhou, Xiangqian
%T A Maximum Resonant Set of Polyomino Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 323-337
%V 36
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a5/
%G en
%F DMGT_2016_36_2_a5
Zhang, Heping; Zhou, Xiangqian. A Maximum Resonant Set of Polyomino Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 323-337. http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a5/

[1] H. Abeledo and G.W. Atkinson, Unimodularity of the Clar number problem, Linear Algebra Appl. 420 (2007) 441-448. doi:10.1016/j.laa.2006.07.026

[2] C. Berge, C.C. Chen, V. Chvátal and C.S. Seow, Combinatorial properties of polyominoes, Combinatorica 1 (1981) 217-224. doi:10.1007/BF02579327

[3] Z. Che and Z. Chen, Forcing on perfect matchings - A survey, MATCH Commun. Math. Comput. Chem. 66 (2011) 93-136.

[4] E. Clar, The Aromatic Sextet (Wiley, London, 1972).

[5] M.E. Fisher, Statistical mechanics of dimers on a plane lattice, Phys. Rev. 124 (1961) 1664-1672. doi:10.1103/PhysRev.124.1664

[6] E.J. Cockayne, Chessboard domination problems, Discrete Math. 86 (1990) 13-20. doi:10.1016/0012-365X(90)90344-H

[7] C.M. Grinstead, B. Hahne and D. Van Stone, On the queen domination problem, Discrete Math. 86 (1990) 21-26. doi:10.1016/0012-365X(90)90345-I

[8] I. Gutman, S.J. Cyvin, Advances in the Theory of Benzenoid Hydrocarbons (Springer, Berlin, 1990). doi:10.1007/3-540-51505-4

[9] F. Harary, D.J. Klein and T.P. Živkovič, Graphical properties of polyhexes: Perfect matching vector and forcing, J. Math. Chem. 6 (1991) 295-306. doi:10.1007/BF01192587

[10] W.C. Herndon, Resonance energies of aromatic hydrocarbons: Quantitative test of resonance theory, J. Am. Chem. Soc. 95 (1973) 2404-2406. doi:10.1021/ja00788a073

[11] P.W. Kasteleyn, The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice, Physica 27 (1961) 1209-1225. doi:10.1016/0031-8914(61)90063-5

[12] X. Ke, A lower bound on the number of elementary components of essentially disconnected generalized polyomino graphs, J. Math. Chem. 50 (2012) 131-140. doi:10.1007/s10910-011-9900-x

[13] D.J. Klein and M. Randić, Innate degree of freedom of a graph, J. Comput. Chem. 8 (1987) 516-521. doi:10.1002/jcc.540080432

[14] W. Li and H. Zhang, Dimer statistics of honeycomb lattices on Klein bottle, Möbius strip and cylinder, Phys. A 391 (2012) 3833-3848. doi:10.1016/j.physa.2012.03.004

[15] S. Liu and J. Ou, On maximal resonance of polyomino graphs, J. Math. Chem. 51 (2013) 603-619. doi:10.1007/s10910-012-0104-9

[16] F. Lu and L. Zhang, Dimers on two types of lattices on the Klein bottle, J. Phys. A 45 (2012) #49. doi:10.1088/1751-8113/45/49/494012

[17] L. Lovász and M.D. Plummer, Matching Theory (Annals of Discrete Mathematics, Vol. 29, North-Holland, Amsterdam, 1986).

[18] A. Motoyama and H. Hosoya, King and domino polynomials for polyomino graphs, J. Math. Phys. 18 (1977) 1485-1490. doi:10.1063/1.523411

[19] L. Pachter and P. Kim, Forcing matchings on square grids, Discrete Math. 190 (1998) 287-294. doi:10.1016/S0012-365X(97)00266-5

[20] M. Randić, Conjugated circuits and resonance energies of benzenoid hydrocarbons, Chem. Phys. Lett. 38 (1976) 68-70. doi:10.1016/0009-2614(76)80257-6

[21] M. Randić, Aromaticity and conjugation, J. Am. Chem. Soc. 99 (1977) 444-450. doi:10.1021/ja00444a022

[22] H. Sachs, Perfect matchings in hexagonal systems, Combinatorica 4 (1980) 89-99. doi:10.1007/BF02579161

[23] H. Sachs and H. Zernitz, Remark on the dimer problem, Discrete Appl. Math. 51 (1994) 171-179. doi:10.1016/0166-218X(94)90106-6

[24] K. Salem and H. Abeledo, A maximal alternating set of a hexagonal system, MATCH Commun. Math. Comput. Chem. 55 (2006) 159-176.

[25] S. Wei and X. Ke, Elementary components of essentially disconnected polyomino graphs, J. Math. Chem. 47 (2010) 496-504. doi:10.1007/s10910-009-9589-2

[26] L. Xu, H. Bian and F. Zhang, Maximum forcing number of hexagonal systems, MATCH Commun. Math. Comput. Chem. 70 (2013) 493-500.

[27] W. Yan, Y.-N. Yeh and F. Zhang, Dimer problem on the cylinder and torus, Phys. A 387 (2008) 6069-6078. doi:10.1016/j.physa.2008.06.042

[28] F. Zhang, X. Guo and R. Chen, The connectivity of Z-transformation graphs of perfect matchings of hexagonal systems, Acta Math. Appl. Sin. 4 (1988) 131-135. doi:10.1007/bf02006061

[29] H. Zhang, The connectivity of Z-transformation graphs of perfect matchings of polyominoes, Discrete Math. 158 (1996) 257-272. doi:10.1016/0012-365X(95)00048-2

[30] H. Zhang and F. Zhang, Perfect matchings of polyomino graphs, Graphs Combin. 13 (1997) 295-304. doi:10.1007/BF03353008

[31] H. Zhang and F. Zhang, Plane elementary bipartite graphs, Discrete Appl. Math. 105 (2000) 291-311. doi:10.1016/S0166-218X(00)00204-3

[32] M. Zheng and R. Chen, A maximal cover of hexagonal systems, Graphs Combin. 1 (1985) 295-298. doi:10.1007/BF02582955