A Maximum Resonant Set of Polyomino Graphs

Heping Zhang; Xiangqian Zhou

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 2, page 323-337
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Heping Zhang, and Xiangqian Zhou. "A Maximum Resonant Set of Polyomino Graphs." Discussiones Mathematicae Graph Theory 36.2 (2016): 323-337. <http://eudml.org/doc/277130>.

@article{HepingZhang2016,
abstract = {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.},
author = {Heping Zhang, Xiangqian Zhou},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {polyomino graph; dimer problem; perfect matching; resonant set; forcing number; alternating set},
language = {eng},
number = {2},
pages = {323-337},
title = {A Maximum Resonant Set of Polyomino Graphs},
url = {http://eudml.org/doc/277130},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Heping Zhang
AU - Xiangqian Zhou
TI - A Maximum Resonant Set of Polyomino Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 2
SP - 323
EP - 337
AB - 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.
LA - eng
KW - polyomino graph; dimer problem; perfect matching; resonant set; forcing number; alternating set
UR - http://eudml.org/doc/277130
ER -

References

top
  1. [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[WoS][Crossref] Zbl1186.05078
  2. [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[Crossref] Zbl0491.05048
  3. [3] Z. Che and Z. Chen, Forcing on perfect matchings - A survey, MATCH Commun. Math. Comput. Chem. 66 (2011) 93-136. Zbl1265.05001
  4. [4] E. Clar, The Aromatic Sextet (Wiley, London, 1972). 
  5. [5] M.E. Fisher, Statistical mechanics of dimers on a plane lattice, Phys. Rev. 124 (1961) 1664-1672. doi:10.1103/PhysRev.124.1664[Crossref] Zbl0105.22403
  6. [6] E.J. Cockayne, Chessboard domination problems, Discrete Math. 86 (1990) 13-20. doi:10.1016/0012-365X(90)90344-H[Crossref] 
  7. [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[Crossref] Zbl0742.05021
  8. [8] I. Gutman, S.J. Cyvin, Advances in the Theory of Benzenoid Hydrocarbons (Springer, Berlin, 1990). doi:10.1007/3-540-51505-4[Crossref] Zbl1125.92326
  9. [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[Crossref] 
  10. [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[Crossref] 
  11. [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[Crossref] Zbl1244.82014
  12. [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[WoS][Crossref] Zbl1238.92070
  13. [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[Crossref] 
  14. [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[Crossref] 
  15. [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[Crossref] Zbl1327.05246
  16. [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[WoS][Crossref] Zbl1257.82027
  17. [17] L. Lovász and M.D. Plummer, Matching Theory (Annals of Discrete Mathematics, Vol. 29, North-Holland, Amsterdam, 1986). 
  18. [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[Crossref] Zbl0359.05004
  19. [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[Crossref] 
  20. [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[Crossref] 
  21. [21] M. Randić, Aromaticity and conjugation, J. Am. Chem. Soc. 99 (1977) 444-450. doi:10.1021/ja00444a022[Crossref] 
  22. [22] H. Sachs, Perfect matchings in hexagonal systems, Combinatorica 4 (1980) 89-99. doi:10.1007/BF02579161[Crossref] 
  23. [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[Crossref] 
  24. [24] K. Salem and H. Abeledo, A maximal alternating set of a hexagonal system, MATCH Commun. Math. Comput. Chem. 55 (2006) 159-176. Zbl1090.05059
  25. [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[WoS][Crossref] Zbl1198.92051
  26. [26] L. Xu, H. Bian and F. Zhang, Maximum forcing number of hexagonal systems, MATCH Commun. Math. Comput. Chem. 70 (2013) 493-500. Zbl1299.05274
  27. [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[Crossref] 
  28. [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[Crossref] 
  29. [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[Crossref] 
  30. [30] H. Zhang and F. Zhang, Perfect matchings of polyomino graphs, Graphs Combin. 13 (1997) 295-304. doi:10.1007/BF03353008[Crossref] Zbl0895.05051
  31. [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[Crossref] 
  32. [32] M. Zheng and R. Chen, A maximal cover of hexagonal systems, Graphs Combin. 1 (1985) 295-298. doi:10.1007/BF02582955[Crossref] Zbl0577.05055

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.