Yanfei Ma; Rui Yang

On the number of Perfect Matchings of Tubular Fullerene Graphs

Full Text (PDF, 1323KB), PP.1-11

Views: 0 Downloads: 0

Author(s)

Yanfei Ma ^1,* Rui Yang ¹

1. School of Mathematics and Information Science, Henan Polytechnic University, Jiaozuo Henan, 454000, China

* Corresponding author.

DOI: https://doi.org/10.5815/ijmsc.2023.03.01

Received: 11 Nov. 2022 / Revised: 27 Dec. 2022 / Accepted: 29 Jan. 2023 / Published: 8 Aug. 2023

Index Terms

Fullerene Graph, Tubular Fullerene, Perfect Matching, Cyclic Edge-cut

Abstract

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 T_n for some integer n >=1, where T_n is the tubular fullerene graph T_ncomprised of two caps formed of six pentagons joined by n concentric layers of hexagons. In this paper, the perfect matchings of the graph T_n 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 T_n is given by recursive relationships. Finally, we get the number of perfect matchings of T_n with P vertices.

Cite This Paper

Yanfei Ma, Rui Yang, "On the number of Perfect Matchings of Tubular Fullerene Graphs", International Journal of Mathematical Sciences and Computing(IJMSC), Vol.9, No.3, pp. 1-11, 2023. DOI:10.5815/ijmsc.2023.03.01

Reference

[1]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.
[2]G. G. Hall, A graphic model of a class of molecules, Int. J. Math. Educ. Sci. Technol. 4 (1973) 233-240.
[3]L. Pauling, The nature of the chemical bond, Cornell. Univ. Press, Ithaca, New York, 1939.
[4]R. Swinborne-Sheldrake, W. C. Herndon, I. Gutman, Kekulé structures and resonance energies of benzennoid hydrocarbons, Tetrahedron Lett. 16 (1975) 755-758.
[5]M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, J. Combin. Theory Ser. A 77 (1997) 67-97.
[6]W. Jockusch, Perfect matchings and perfect squares, J. Combin. Theory Ser. A 67 (1994) 100-115.
[7]W. Yan, F. Zhang, Enumeration of perfect matchings of a type of Cartesian products of graphs, Discrete Appl. Math. 154 (2006) 145-157.
[8]W. Yan, F. Zhang, Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians, Advances in Appl. Math. 32 (2004) 655-668.
[9]L. G. Valiant, The complexity of computing the permanent, Theoret.Comput. Sci. 8 (1979)189-201.
[10]P. W. Kasteleyn, Dimer statistics and phase transition, J. Math. Phys. 4 (1963) 287-293.
[11]W. Lu, F. Wu, Dimer statistics on the Möbius strip and the Klein bottle, Phys. Lett. A, 259 (1999) 108-114.
[12]W. Lu, F. Wu, Close-packed dimers on nonorientable surfaces, Phys. Lett. A, 293 (2002) 235-246.
[13]B. Tang, H. Ren, Recursive method for perfect matching numbers by Matching vertex classification, J. Jilin Univ. (Sci. Edi.), 57 (2019) 285-290.
[14]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.
[15]H. W. Kroto, J. R. Heath, et al., C60: Buckminsterfullerene, nature, 318 (1985) 162-163.
[16]J. Petersen, Die Theorie der regulären graphs, Acta. Math. 15 (1891) 193-220.
[17]D. J. Klein, X. Liu, Theorems for carbon cages, J. Math. Chem. 11 (1992) 199-205.
[18]T. Došlić, On lower bounds of number of perfect matchings in fullerene graphs, J. Math. Chem. 24 (1998) 359-364.
[19]H. Zhang, F. Zhang, New lower bound on the number of perfect matchings in fullerene graphs, J. Math. Chem. 30 (2001) 343-347.
[20]F. Kardoš, D. Král, J. Miškuf, et al., Fullerene graphs have exponentially many perfect matchings, J. Math. Chem. 46 (2009) 443-447.
[21]F. Kardoš, R. škrekovski, Cyclic edge-cuts in fullerene graphs, J. Math. Chem. 44 (2008) 121-132.
[22]K. Kutnar, D. Marušič, On cyclic edge-connectivity of fullerenes, Discrete Appl. Math. 156 (2008) 1661-1669.

International Journal of Mathematical Sciences and Computing (IJMSC)