×

Single coronoid systems with an anti-forcing edge. (English) Zbl 1372.05173

Summary: An edge of a graph \(G\) is called an anti-forcing edge (or forcing single edge) if \(G\) has a unique perfect matching not containing this edge. It has been known for two decades that a hexagonal system has an anti-forcing edge if and only if it is a truncated parallelogram. A connected subgraph \(G\) of a hexagonal system is called a single coronoid system if \(G\) has exactly one non-hexagonal interior face and each edge belongs to a hexagon of \(G\). In this paper, we show that a single coronoid system with an anti-forcing edge can be obtained by gluing a truncated parallelogram with a generalized hexagonal system which has a unique perfect matching and can be obtained by attaching two additional pendant edges to a hexagonal system, and the latter can be constructed from one hexagon case by applying five modes of hexagon addition. Such graphs are half essentially disconnected coronoid systems in the rheo classification. So computing the number of perfect matchings of such graphs is reduced to that of two hexagonal systems.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abeledo, H.; Atkinson, G. W., A min-max theorem for plane bipartite graphs, Discrete Appl. Math., 158, 375-378 (2010) · Zbl 1225.05197
[2] Chen, R., Coronoid systems with perfect matchings, Discrete Appl. Math., 64, 117-133 (1996) · Zbl 0846.05067
[3] Chen, R.; Zhang, F., Coronoid systems with fixed bonds, J. Mol. Struct., 403, 237-243 (1997)
[4] Chen, R.; Zhang, F., Regular coronoid systems, Discrete Appl. Math., 74, 147-158 (1997) · Zbl 0869.05061
[5] Cyvin, S. J.; Brunvoll, J.; Cyvin, B. N., (Theory of Coronoid Hydrocarbons. Theory of Coronoid Hydrocarbons, Lecture Notes in Chemistry, vol. 54 (1991), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0665.05051
[6] Cyvin, S. J.; Brunvoll, J.; Cyvin, B. N.; Zhang, F. J., (Theory of Coronoid Hydrocarbons II. Theory of Coronoid Hydrocarbons II, Lecture Notes in Chemistry, vol. 62 (1994), Springer-Verlag: Springer-Verlag Berlin)
[7] Cyvin, S. J.; Gutman, I., (Kekulé Structures in Benzenoid Hydrocarbons. Kekulé Structures in Benzenoid Hydrocarbons, Lecture Notes in Chemistry, vol. 46 (1988), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0663.05028
[8] Deng, H., The anti-forcing number of hexagonal chains, MATCH Commun. Math. Comput. Chem., 58, 675-682 (2007) · Zbl 1142.05354
[9] Deng, H., The anti-forcing number of double hexagonal chains, MATCH Commun. Math. Comput. Chem., 60, 183-192 (2008) · Zbl 1199.05282
[10] Dewar, M. S.J.; Longuet-Higgins, H. C., The correspondence between the resonance and molecular orbital theories, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 214, 482-493 (1952) · Zbl 0046.44505
[11] Gutman, I.; Cyvin, S. J., Introduction to the Theory of Benzenoid Hydrocarbons (1989), Springer: Springer Berlin · Zbl 0722.05056
[12] Hansen, P.; Zheng, M., Bonds fixed by fixing bonds, J. Chem. Inf. Comput. Sci., 34, 297-304 (1994)
[13] Harary, F.; Klein, D. J.; Živković, T. P., Graphical properties of polyhexes: perfect matching vector and forcing, J. Math. Chem., 6, 295-306 (1991)
[14] Klein, D. J.; Randić, M., Innate degree of freedom of a graph, J. Comput. Chem., 8, 516-521 (1987)
[15] Lei, H.; Yeh, Y.-N.; Zhang, H., Anti-forcing numbers of perfect matchings of graphs, Discrete Appl. Math., 202, 95-105 (2016) · Zbl 1330.05131
[16] Li, X., Hexagonal systems with forcing single edges, Discrete Appl. Math., 72, 295-301 (1997) · Zbl 0865.05069
[17] Lovász, L.; Plummer, M., Matching Theory (1986), North-Holland: North-Holland Amsterdam · Zbl 0618.05001
[18] Sachs, H., Perfect matchings in hexagonal systems, Combinatorica, 4, 89-99 (1984) · Zbl 0542.05048
[19] Shiu, W. C.; Lam, P. C.B.; Zhang, F.; Zhang, H., Normal components, Kekulé patterns, and Clar patterns in plane bipartite graphs, J. Math. Chem., 31, 405-420 (2002) · Zbl 1017.92046
[20] Vukičević, D.; Trinajstić, N., On the anti-forcing number of benzenoids, J. Math. Chem., 42, 575-583 (2007) · Zbl 1127.92054
[21] Vukičević, D.; Trinajstić, N., On the anti-Kekulé number and anti-forcing number of cata-condensed benzenoids, J. Math. Chem., 43, 719-726 (2008) · Zbl 1196.92062
[22] Yang, Q.; Zhang, H.; Lin, Y., On the anti-forcing number of fullerene graphs, MATCH Commun. Math. Comput. Chem., 74, 673-692 (2015) · Zbl 1462.05344
[23] Zhang, F.; Li, X., Hexagonal systems with forcing edges, Discrete Math., 140, 253-263 (1995) · Zbl 0832.05090
[24] Zhang, F.; Li, X., Forcing bonds of a benzenoid system, Acta Math. Appl. Sin., 12, 209-215 (1996) · Zbl 0861.92022
[25] Zhang, H.; Deng, K., Spectrum of matching forcing numbers of a hexagonal system with a forcing edge, MATCH Commun. Math. Comput. Chem., 73, 457-471 (2015) · Zbl 1464.05312
[26] Zhang, H.; Ye, D.; Shiu, W., Forcing matching numbers of fullerene graphs, Discrete Appl. Math., 158, 573-582 (2010) · Zbl 1215.05139
[27] Zhang, F.; Zhang, H., A note on the number of perfect matchings of bipartite graphs, Discrete Appl. Math., 73, 275-282 (1997) · Zbl 0870.05068
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.