On the number of Perfect Matchings of Tubular Fullerene Graphs
Автор: Yanfei Ma, Rui Yang
Журнал: International Journal of Mathematical Sciences and Computing @ijmsc
Статья в выпуске: 3 vol.9, 2023 года.
Бесплатный доступ
The perfect matchings counting problem of graphs has important applications in combinatorial optimization, statistical physics, quantum chemistry and other fields. A perfect matching of a graph G is a set of non-adjacent edges that covers all vertices of G . The number of perfect matchings of a graph is closely related to its number of vertices. A fullerene graph is a 3-connected cubic planar graphs all of whose faces are pentagons and hexagons. Došlić obtained that a fullerene graph with P vertices has at least P/2+1 perfect matchings, Zhang et al. proved a better lower bound 3(p+2)/4 of the number of perfect matchings of a fullerene graph. We have known that the fullerene graph has a nontrivial cyclic 5-edge-cut if and only if it is isomorphic to the graph Tn for some integer n >=1, where Tn is the tubular fullerene graph Tn comprised of two caps formed of six pentagons joined by n concentric layers of hexagons. In this paper, the perfect matchings of the graph Tn is classified by matching a certain vertex, and recursive relations of a set of perfect matching numbers are obtained. Then the calculation formula of the number of perfect matchings of the graph Tn is given by recursive relationships. Finally, we get the number of perfect matchings of Tn with P vertices.
Fullerene Graph, Tubular Fullerene, Perfect Matching, Cyclic Edge-cut
Короткий адрес: https://sciup.org/15019055
IDR: 15019055 | DOI: 10.5815/ijmsc.2023.03.01
Список литературы On the number of Perfect Matchings of Tubular Fullerene Graphs
- J. Propp, Kutnar Enumerations of matchings: problems and progress, in: L. Billera, A. Björner, C. Greene, R. Simeon, and RP Stanley(Eds), New Perspectives in Geometric Combinatorics, Cam. Univ. Press, Cambridge, (1999) 255-291.
- G. G. Hall, A graphic model of a class of molecules, Int. J. Math. Educ. Sci. Technol. 4 (1973) 233-240.
- L. Pauling, The nature of the chemical bond, Cornell. Univ. Press, Ithaca, New York, 1939.
- R. Swinborne-Sheldrake, W. C. Herndon, I. Gutman, Kekulé structures and resonance energies of benzennoid hydrocarbons, Tetrahedron Lett. 16 (1975) 755-758.
- M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, J. Combin. Theory Ser. A 77 (1997) 67-97.
- W. Jockusch, Perfect matchings and perfect squares, J. Combin. Theory Ser. A 67 (1994) 100-115.
- W. Yan, F. Zhang, Enumeration of perfect matchings of a type of Cartesian products of graphs, Discrete Appl. Math. 154 (2006) 145-157.
- W. Yan, F. Zhang, Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians, Advances in Appl. Math. 32 (2004) 655-668.
- L. G. Valiant, The complexity of computing the permanent, Theoret.Comput. Sci. 8 (1979)189-201.
- P. W. Kasteleyn, Dimer statistics and phase transition, J. Math. Phys. 4 (1963) 287-293.
- W. Lu, F. Wu, Dimer statistics on the Möbius strip and the Klein bottle, Phys. Lett. A, 259 (1999) 108-114.
- W. Lu, F. Wu, Close-packed dimers on nonorientable surfaces, Phys. Lett. A, 293 (2002) 235-246.
- B. Tang, H. Ren, Recursive method for perfect matching numbers by Matching vertex classification, J. Jilin Univ. (Sci. Edi.), 57 (2019) 285-290.
- B. Tang, H. Ren, Perfect matching number of two kinds of graphs based on recursive method of Matching vertex classification, J. Jilin Univ. (Sci. Edi.), 58 (2020) 309-313.
- H. W. Kroto, J. R. Heath, et al., C60: Buckminsterfullerene, nature, 318 (1985) 162-163.
- J. Petersen, Die Theorie der regulären graphs, Acta. Math. 15 (1891) 193-220.
- D. J. Klein, X. Liu, Theorems for carbon cages, J. Math. Chem. 11 (1992) 199-205.
- T. Došlić, On lower bounds of number of perfect matchings in fullerene graphs, J. Math. Chem. 24 (1998) 359-364.
- H. Zhang, F. Zhang, New lower bound on the number of perfect matchings in fullerene graphs, J. Math. Chem. 30 (2001) 343-347.
- F. Kardoš, D. Král, J. Miškuf, et al., Fullerene graphs have exponentially many perfect matchings, J. Math. Chem. 46 (2009) 443-447.
- F. Kardoš, R. škrekovski, Cyclic edge-cuts in fullerene graphs, J. Math. Chem. 44 (2008) 121-132.
- K. Kutnar, D. Marušič, On cyclic edge-connectivity of fullerenes, Discrete Appl. Math. 156 (2008) 1661-1669.
