On the Estrada Index of Point Attaching Strict $k$-Quasi Tree Graphs

Download PDF


DOI: 10.46793/KgJMat2002.165I


Let G = (V,E) be a finite and simple graph with λ12,n as its eigenvalues. The Estrada index of G is EE(G) = i=1neλi. For a positive integer k, a connected graph G is called strict k-quasi tree if there exists a set U of vertices of size k such that G U is a tree and this is as small as possible with this property. In this paper, we define point attaching strict k-quasi tree graphs and obtain the graph with minimum Estrada index among point attaching strict k-quasi tree graphs with k even cycles.


Estrada Index, quasi tree graph, point attaching Strict k-quasi tree graph.


[1]   N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1993.

[2]   D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and Application, Academic Press, New York, 1980.

[3]   H. Deng, A proof of a conjecture on the estrada index, MATCH Commun. Math. Comput. Chem. 62 (2009), 599–606.

[4]   E. Deutsch and S. Klavzar, Computing the hosoya polynomial of graphs from primary subgraphs, MATCH Commun. Math. Comput. Chem. 70 (2013), 627–644.

[5]   Z. Du and B. Zhou, The estrada index of unicyclic graphs, Linear Algebra Appl. 436 (2012), 3149–3159.

[6]   E. Estrada, Characterization of 3d molecular structure, Chemical Physics Letters 319 (2000), 713–718.

[7]   E. Estrada, Characterization of the folding degree of proteins, Bioinformatics 18 (2002), 697–704.

[8]   E. Estrada and J. A. Rodriguez-Velazquez, Subgraph centrality in complex networks, Phys. Rev. E 71 (2005), Paper ID 056103.

[9]   I. Gutman and A. Graovac, Estrada index of cycles and paths, Chemical Physics Letters 436 (2007), 294–296.

[10]   A. Ilić and D. Stevanović, The estrada index of chemical trees, J. Math. Chem. 47(1) (2010), 305–314.

[11]   F. Li, L. Wei, J. Cao, F. Hu and H. Zhao, On the maximum estrada index of 3-uniform linear hypertrees, Scientific World Journal (2014), DOI 10.1155/2014/637865.

[12]   F. Li, L. Wei, H. Zhao, F. Hu and X. Ma, On the estrada index of cactus graphs, Discrete Appl. Math. 203 (2016), 94–105.

[13]   J. Li, X. Li and L. Wang, The minimal estrada index of trees with two maximum degree vertices, MATCH Commun. Math. Comput. Chem 64 (2010), 799–810.

[14]   M. Lu and J. Gao, On the randić index of quasi-tree graphs, J. Math. Chem. 42 (2007), 297–310.

[15]   Y. Shang, Biased edge failure in scale-free networks based on natural connectivity, Indian Journal of Physics 86 (2012), 485–488.

[16]   Y. Shang, Random lifts of graphs: network robustness based on the estrada index, Appl. Math. E-Notes 12 (2012), 53–61.

[17]   R. P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Annals of the New York Academy of Sciences 576 (1989), 500–535.

[18]   K. Xu, J. Wang and H. Liu, The harary index of ordinary and generalized quasi-tree graphs, J. Appl. Math. Comput. 45 (2014), 365–374.

[19]   J. Zhang, B. Zhou and J. Li, On estrada index of trees, Linear Algebra Appl. 434 (2011), 215–223.