Relationship between Coefficients of Characteristic Polynomial and Matching Polynomial of Regular Graphs and its Applications

Document Type : Research Paper


University of Kashan


ABSTRACT. Suppose G is a graph, A(G) its adjacency matrix and f(G, x)=x^n+a_(n-1)x^(n-1)+... is the characteristic polynomial of G. The matching polynomial of G is defined as M(G, x) = x^n-m(G,1)x^(n-2) + ... where m(G,k) is the number of k-matchings in G. In this paper, we determine the relationship between 2k-th coefficient of characteristic polynomial, a_(2k), and k-th coefficient of matching polynomial, (-1)^km(G, k), in a regular graph. In the rest of this paper, we apply these relations for finding 5,6-matchings of fullerene graphs.


Main Subjects

1. A. R. Ashrafi and G. H. FathTabar, Bounds on the Estrada index of ISR (4, 6)–
fullerenes, Appl. Math. Lett. 24 (2011) 337–339.
2. A. Behmaram, Matching in Fullerene and Molecular Graphs, Ph.D. thesis,
University of Tehran, 2013.
3. A. Behmaram, T. Došlić and S. Friedland, Matchings in m–generalized fullerene
graphs, Ars Math. Contemp. 11 (2016) 301–313.
4. A. Behmaram, H. Yousefi Azari and A. R. Ashrafi, Closed formulas for the number
of small paths, independent sets and matchings in fullerenes, Appl. Math. Lett. 25
(2012) 1721–1724.
5. A. Behmaram, On the number of 4matchings in graphs, MATCH Commun. Math.
Comput. Chem. 62 (2009) 381–388.
6. N. Biggs, Algebraic Graph Theory, Cambridge Univ. Press, Cambridge, 1974.
7. D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and
Applications, Academic Press, New York, 1980.
8. M. Deza, M. Dutour and P. W. Fowler, Zigzags, railroads and knots in fullerenes,
J. Chem. Inf. Comp. Sci. 44 (2004) 1282–1293.
9. E. J. Farrell, An introduction to matching polynomials, J. Combin. Theory Ser. B 27
(1979) 75–86.
10. G. H. FathTabar, A. R. Ashrafi and I. Gutman, Note on Estrada and L-Estrada
indices of graphs, Bull. Cl. Sci. Math. Nat. Sci. Math. 34 (2009) 1–16.
11. G. H. FathTabar, A. R. Ashrafi and D. Stevanović, Spectral properties of
fullerenes, J. Comput. Theor. Nanosci. 9 (2012) 327–329.
12. P. W. Fowler and D. E. Manolopoulos, An Atlas of Fullerenes, Oxford Univ. Press,
Oxford, 1995.
13. M. Ghorbani and E. BaniAsadi, Remarks on characteristic coefficients of
fullerene graphs, Appl. Math. Comput. 230 (2014) 428–435.
14. H. W. Kroto, J. R. Heath, S. C. O’Brien, R. F. Curl and R. E. Smalley, C60:
buckminsterfullerene, Nature 318 (1985) 162–163.
15. Z. Mehranian, A. Gholami and A. R. Ashrafi, Experimental results on the symmetry
and topology of 3 and 4generalized fullerenes, J. Comput. Theor. Nanosci. 11
(2014) 1–6.
16. W. Myrvold, B. Bultena, S. Daugherty, B. Debroni, S. Girn, M. Minchenko, J.
Woodcock and P. W. Fowler, FuiGui: A graphical user interface for investigating
conjectures about fullerenes, MATCH Commun. Math. Comput. Chem. 58 (2007)
17. P. Schwerdtfeger, L. Wirz and J. Avery, Program fullerene: a software package for
constructing and analyzing structures of regular fullerenes, J. Comput. Chem. 34
(2013) 1508–1526.
18. M. D. Sikirić and M. Deza, Space fullerenes; computer search for new
FrankKasper structures II, Structural Chemistry, 23 (2012) 1103–1114.
19. M. D. Sikirić, O. DelgadoFriedrichs and M. Deza, Space fullerenes: a computer
search for new Frank–Kasper structures, Acta Crystallogr. A 66 (2010) 602–615.
20. F. Taghvaee and A. R. Ashrafi, Ordering some regular graphs with respect to
spectral moments, submitted.
21. F. Taghvaee and A. R. Ashrafi, On spectrum of Igraphs and its ordering with
respect to spectral moments, submitted.
22. F. Taghvaee and A. R. Ashrafi, Comparing fullerenes by spectral moments, J.
Nanosci. Nanotechnol. 16 (2016) 3132–3135.
23. F. Taghvaee and G. H. FathTabar, Signless Laplacian spectral moments of graphs
and ordering some graphs with respect to them, Alg. Struc. Appl. 1 (2014) 133–141.
24. R. Vesalian and F. Asgari, Number of 5-matching in graphs, MATCH Commun.
Math. Comput. Chem. 69 (2013) 33–46.