Document Type: Research Paper

**Authors**

University of Kashan

**Abstract**

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.

**Keywords**

**Main Subjects**

1. A. R. Ashrafi and G. H. FathTabar, 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 4matchings 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.

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 4matchings 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. FathTabar, 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. FathTabar, 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. BaniAsadi, 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 4generalized 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)

403–422.

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

FrankKasper structures II, Structural Chemistry, 23 (2012) 1103–1114.

19. M. D. Sikirić, O. DelgadoFriedrichs 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 Igraphs 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. FathTabar, 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.

indices of graphs, Bull. Cl. Sci. Math. Nat. Sci. Math. 34 (2009) 1–16.

11. G. H. FathTabar, 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. BaniAsadi, 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 4generalized 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)

403–422.

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

FrankKasper structures II, Structural Chemistry, 23 (2012) 1103–1114.

19. M. D. Sikirić, O. DelgadoFriedrichs 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 Igraphs 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. FathTabar, 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.

Volume 8, Issue 1

Winter 2017

Pages 7-23