Anti-forcing spectrum of any cata-condensed hexagonal system is continuous

Abstract

The anti-forcing number of a perfect matching M of a graph G is the minimal number of edges not in M whose removal makes M a unique perfect matching of the resulting graph. The anti-forcing spectrum of G is the set of anti-forcing numbers over all perfect matchings of G: In this paper, we prove that the anti-forcing spectrum of any cata-condensed hexagonal system is continuous, that is, it is a finite set of consecutive integers.

Keywords

Perfect matching / anti-forcing number / anti-forcing spectrum / hexagonal system

References

[1] Adams P, Mahdian M, Mahmoodian E S. On the forced matching numbers of bipartite graphs. Discrete Math, 2004, 281: 1–12

[2] Afshani P, Hatami H, Mahmoodian E S. On the spectrum of the forced matching number of graphs. Australas J Combin, 2004, 30: 147–160

[3] Che Z, Chen Z. Forcing on perfect matchings|A survey. MATCH Commun Math Comput Chem, 2011, 66: 93–136

[4] Cyvin S J, Gutman I. Kekulé Structures in Benzenoid Hydrocarbons. Lecture Notes in Chemistry, Vol 46. Berlin: Springer, 1988

[5] Deng H. The anti-forcing number of hexagonal chains. MATCH Commun Math Comput Chem, 2007, 58: 675–682

[6] Deng H. The anti-forcing number of double hexagonal chains. MATCH Commun Math Comput Chem, 2008, 60: 183–192

[7] Deng K, Zhang H. Anti-forcing spectra of perfect matchings of graphs. J Comb Optim, 2015,

[8] Fries K. Uber byclische verbindungen und ihren vergleich mit dem naphtalin. Ann Chem, 1927, 454: 121–324

[9] Harary F, Klein D, Živković T. Graphical properties of polyhexes: perfect matching vector and forcing. J Math Chem, 1991, 6: 295–306

[10] Jiang X, Zhang H. On forcing matching number of boron-nitrogen fullerene graphs. Discrete Appl Math, 2011, 159: 1581–1593

[11] Jiang X, Zhang H. The maximum forcing number of cylindrical grid, toroidal 4-8 lattice and Klein bottle 4-8 lattice. J Math Chem, 2016, 54: 18–32

[12] Klein D, Randić M. Innate degree of freedom of a graph. J Comput Chem, 1987, 8:516–521

[13] Lam F, Pachter L. Forcing number for stop signs. Theoret Comput Sci, 2003, 303:409–416

[14] Lei H, Yeh Y, Zhang H. Anti-forcing numbers of perfect matchings of graphs. Discrete Appl Math, 2016, 202: 95–105

[15] Lovász L, Plummer M. Matching Theory. Annals of Discrete Mathematics, Vol 29. Amsterdam: North-Holland, 1986

[16] Pachter L, Kim P.Forcing matchings on square grids. Discrete Math, 1998, 190: 287–294

[17] Randić M, Vukičević D. Kekulé structures of fullerene C70: Croat Chem Acta, 2006, 79: 471–481

[18] Riddle M E. The minimum forcing number for the torus and hypercube. Discrete Math, 2002, 245: 283–292

[19] Shi L, Zhang H. Forcing and anti-forcing numbers of (3, 6)-fullerenes. MATCH Commun Math Comput Chem, 2016, 76: 597–614

[20] Vukičević D, Gutman I, Randić M. On instability of fullerene C72: Croat Chem Acta, 2006, 79: 429–436

[21] Vukičcević D, Randić M. On Kekuklé structures of buckminsterfullerene. Chem Phys Lett, 2005, 401: 446–450

[22] Vukičević D, Trinajstié N. On the anti-forcing number of benzenoids. J Math Chem, 2007, 42: 575–583

[23] Vukičević D, Trinajstié N. On the anti-kekulé number and anti-forcing number of cata-condensed benzenoids. J Math Chem, 2008, 43: 719–726

[24] Wang H, Ye D, Zhang H. The forcing number of toroidal polyhexes. J Math Chem, 2008, 43: 457–475

[25] Xu L, Bian H, Zhang F. Maximum forcing number of hexagonal systems. MATCH Commun Math Comput Chem, 2013, 70: 493–500

[26] Yang Q, Zhang H, Lin Y. On the anti-forcing number of fullerene graphs. MATCH Commun Math Comput Chem, 2015, 74: 681–700

[27] Zhang F, Guo X, Chen R. Z-transformation graphs of perfect matchings of hexagonal systems. Discrete Math, 1988, 72: 405–415

[28] Zhang H, Deng K. Forcing spectrum of a hexagonal system with a forcing edge. MATCH Commun Math Comput Chem, 2015, 73: 457–471

[29] Zhang H, Yao H, Yang D. A min-max result on outerplane bipartite graphs. Appl Math Lett, 2007, 20: 199–205

[30] Zhang H, Ye D, Shiu W C. Forcing matching numbers of fullerene graphs. Discrete Appl Math, 2010, 158: 573–582

[31] Zhang H, Zhang F. Plane elementary bipartite graphs. Discrete Appl Math, 2000, 105: 291–311

[32] Zhang Q, Bian H, Vumar E. On the anti-kekulé and anti-forcing number of cata-condensed phenylenes. MATCH Commun Math Comput Chem, 2011, 65: 799–806

[33] Zhou X, Zhang H. Clar sets and maximum forcing numbers of hexagonal systems. MATCH Commun Math Comput Chem, 2015, 74: 161–174

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg