×

Relationship between coefficients of characteristic polynomial and matching polynomial of regular graphs and its applications. (English) Zbl 1406.92785

Summary: Suppose \(G\) is a graph, \(A(G)\) its adjacency matrix and \(\psi(G, \lambda)=\lambda^n+a_1\lambda_{n-1}+\dots +a_n\) is the characteristic polynomial of \(G\). The matching polynomial of \(G\) is defined as \(M(G, x) = m(G,0)x^n-m(G,1)x^{n-2} + \dots\), 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, and \((-1)^km(G, k)\), \(k=0,1,2,\dots,\) in a regular graph. In addition, these relations for finding \(5,6\)-matchings of fullerene graphs are applied.

MSC:

92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
05C31 Graph polynomials
05C90 Applications of graph theory

Software:

FuiGui; Fullerene
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. R. Ashrafi and G. H. FathTabar{\it , }Bounds on the Estrada index of ISR (4, 6)-fullerenes, {\it Appl. Math. Lett.}24 (2011)337-339. · Zbl 1203.05089
[2] A. Behmaram{\it , 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, {\it Ars Math. Contemp}. 11 (2016)301-313. · Zbl 1355.05193
[4] A. Behmaram, H. Yousefi Azari and A. R. Ashrafi{\it , }Closed formulas for the number of small paths, independent sets and matchings in fullerenes, {\it Appl. Math. Lett.}25(2012) 1721-1724. · Zbl 1251.05118
[5] A. Behmaram, On the number of 4matchings in graphs, {\it MATCH Commun. Math. }{\it Comput. Chem.}62 (2009) 381-388. · Zbl 1199.05277
[6] N. Biggs, {\it Algebraic Graph Theory}, Cambridge Univ. Press, Cambridge, 1974. · Zbl 0284.05101
[7] D. M. Cvetković, M. Doob and H. Sachs, {\it Spectra of Graphs: Theory and }{\it Applications}, Academic Press, New York, 1980. · Zbl 0458.05042
[8] M. Deza, M. Dutour and P. W. Fowler, Zigzags, railroads and knots in fullerenes, {\it J. Chem. Inf. Comp. Sci.}44 (2004) 1282-1293. {\it }
[9] E. J. Farrell, An introduction to matching polynomials, {\it J. Combin. Theory Ser.}{\it }{\it B}27 (1979) 75-86. {\it Characteristic Polynomial and Matching Polynomial} 23 · Zbl 0335.05131
[10] G. H. FathTabar, A. R. Ashrafi and I. Gutman, Note on Estrada and L-Estrada indices of graphs, {\it Bull. Cl. Sci. Math. Nat. Sci. Math.} 34 (2009) 1-16. · Zbl 1274.05292
[11] G. H. FathTabar, A. R. Ashrafi and D. Stevanović{\it , }Spectral properties of fullerenes,{\it J. Comput. Theor. Nanosci. }9 (2012) 327-329{\it . }
[12] P. W. Fowler and D. E. Manolopoulos, {\it An Atlas of Fullerenes}, Oxford Univ. Press, Oxford, 1995.
[13] M. Ghorbani and E. BaniAsadi, Remarks on characteristic coefficients of fullerene graphs, {\it Appl. Math. Comput}. 230 (2014) 428-435. · Zbl 1410.92174
[14] H. W. Kroto, J. R. Heath, S. C. O’Brien, R. F. Curl and R. E{\it . }Smalley{\it , }C60: buckminsterfullerene{\it , Nature }318 (1985){\it }162-163{\it . }
[15] Z. Mehranian, A. Gholami and A. R. Ashrafi, Experimental results on the symmetry and topology of 3 and 4generalized fullerenes, {\it 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, {\it MATCH Commun. Math. Comput. Chem.}58 (2007) 403-422. · Zbl 1150.92365
[17] P. Schwerdtfeger, L. Wirz and J. Avery, Program fullerene: a software package for constructing and analyzing structures of regular fullerenes, {\it J. Comput. Chem.}34(2013) 1508-1526.
[18] M. D. Sikirić and M. Deza{\it , }Space fullerenes; computer search for new FrankKasper structures II, {\it Structural Chemistry}, 23 (2012) 1103-1114{\it .}
[19] M. D. Sikirić, O. DelgadoFriedrichs and M. Deza, Space fullerenes: a computer search for new Frank-Kasper structures, {\it Acta Crystallogr}. A 66 (2010) 602-615. · Zbl 1370.82015
[20] F. Taghvaee and A. R. Ashrafi, Ordering some regular graphs with respect to spectral moments, submitted. · Zbl 1400.05150
[21] F. Taghvaee and A. R. Ashrafi, On spectrum of Igraphs and its ordering with respect to spectral moments, submitted.{\it } · Zbl 1400.05150
[22] F. Taghvaee and A. R. Ashrafi, Comparing fullerenes by spectral moments, {\it J. }{\it 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, {\it Alg. Struc. Appl.}1 (2014) 133-141. · Zbl 1463.05358
[24] {\it }R. Vesalian and F. Asgari{\it , }Number of 5-matching in graphs{\it , MATCH Commun. }{\it Math. Comput. Chem. }69 (2013) 33-46. · Zbl 1299.05271
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.