×

A bound on the spectral radius of graphs in terms of their Zagreb indices. (English) Zbl 1472.05096

Let \(G=(V,E)\) be a connected and simple graph with \(n\) vertices, \(m\) edges and adjacency matrix \(A\). Denote by \(\lambda_1\geq \dots \geq \lambda_n\) the eigenvalues of \(A\). An eigenvalue is called main if its eigenspace is not perpendicular to the all-one vector \(j\). E. M. Hagos [Linear Algebra Appl. 356, No. 1–3, 103–111 (2002; Zbl 1015.05051)] proved that the number of main eigenvalues of \(G\) equals the largest \(k\) such that \(j,Aj,\dots,A^{k-1}j\) are linearly independent.
For a vertex \(v\in V\), denote by \(d_v\) its degree. The first Zagreb index of \(G\) is defined as \[ M_1=\sum_{v\in V}d_v^2=j^TA^2j, \] and the second Zagreb index of \(G\) is defined as: \[ M_2=\sum_{uv\in E}d_ud_v=\frac{j^TA^3j}{2}. \]
Let \(\alpha=\frac{2(nM_2-mM_1)}{nM_1-4m^2}\) and \(\beta=\frac{M_1^2-4mM_2}{nM_1-4m^2}\). The main result of this paper is that \[ \lambda_1\geq \frac{\alpha+\sqrt{\alpha^2+4\beta}}{2}, \] with equality if and only if \(G\) has exactly two main eigenvalues. Explicit comparisons with other bounds on \(\lambda_1\) are also provided in the paper.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C09 Graphical indices (Wiener index, Zagreb index, Randić index, etc.)
05C07 Vertex degrees

Citations:

Zbl 1015.05051

Software:

Eigensolve
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdo, H.; Dimitrov, D.; Reti, T.; Stevanović, D., Estimating the spectral radius of a graph by the second Zagreb index, MATCH Commun. Math. Comput. Chem., 72, 741-751 (2014) · Zbl 1464.05049
[2] Berman, A.; Zhang, X. D., On the spectral radius of graphs with cut vertices, J. Comb. Theory, Ser. B, 83, 233-240 (2001) · Zbl 1023.05098
[3] Bini, D. A.; Robol, L., Solving secular and polynomial equations: a multiprecision algorithm, J. Comput. Appl. Math., 272, 276-292 (2014) · Zbl 1310.65052
[4] Cao, D., Bounds on eigenvalues and chromatic numbers, Linear Algebra Appl., 270, 1-13 (1998) · Zbl 0894.05041
[5] Chen, L.; Huang, Q., The existence of the graphs that have exactly two main eigenvalues (2016)
[6] Cvetković, D. M., The main part of the spectrum, divisors and switching of graphs, Publ. Inst. Math. (Belgr.), 23, 37, 31-38 (1978) · Zbl 0423.05028
[7] Cvetković, D.; Rowlinson, P.; Simić, S., An Introduction to the Theory of Graph Spectra (2009), Cambridge University Press: Cambridge University Press Cambridge
[8] Dress, A.; Grünewald, S., Semiharmonic trees and monocyclic graphs, Appl. Math. Lett., 16, 1329-1332 (2003) · Zbl 1039.05050
[9] Dress, A.; Stevanović, D., Hoffman-type identities, Appl. Math. Lett., 16, 297-302 (2003) · Zbl 1041.05048
[10] Fan, X.; Luo, Y.; Gao, X., Tricyclic graphs with exactly two main eigenvalues, Cent. Eur. J. Math., 11, 1800-1816 (2013) · Zbl 1277.05107
[11] Favaron, O.; Mahéo, M.; Saclé, J. F., Some eigenvalue properties in graphs (conjectures of Graffiti-II), Discrete Math., 111, 197-220 (1993) · Zbl 0785.05065
[12] Fortune, S., An iterated eigenvalue algorithm for approximating roots of univariate polynomials, J. Symb. Comput., 33, 627-646 (2002) · Zbl 1004.65060
[13] Gutman, I.; Trinajstić, N., Graph theory and molecular orbitals. Total π-electron energy of alternant hydrocarbons, Chem. Phys. Lett., 17, 535-538 (1972)
[14] Gutman, I.; Ruščić, B.; Trinajstić, N.; Wilcox, C. F., Graph theory and molecular orbitals. XII. Acyclic polyenes, J. Chem. Phys., 62, 3399-3405 (1975)
[15] Hagos, E. M., Some results on graph spectra, Linear Algebra Appl., 356, 103-111 (2002) · Zbl 1015.05051
[16] Hayat, S.; Koolen, J. H.; Liu, F.; Qiao, Z., A note on graphs with exactly two main eigenvalues, Linear Algebra Appl., 511, 318-327 (2016) · Zbl 1347.05115
[17] Hofmeister, M., Spectral radius and degree sequence, Math. Nachr., 139, 37-44 (1988) · Zbl 0695.05046
[18] Hong, Y.; Zhang, X. D., Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrix of trees, Discrete Math., 296, 187-197 (2005) · Zbl 1068.05044
[19] Hou, Y.; Tang, Z.; Shiu, W. C., Some results on graphs with exactly two main eigenvalues, Appl. Math. Lett., 25, 1274-1278 (2012) · Zbl 1248.05112
[20] Hou, Y.; Tian, F., Unicyclic graphs with exactly two main eigenvalues, Appl. Math. Lett., 19, 1143-1147 (2006) · Zbl 1172.05336
[21] Hu, Z.; Li, S.; Zhu, C., Bicyclic graphs with exactly two main eigenvalues, Linear Algebra Appl., 431, 1848-1857 (2009) · Zbl 1175.05085
[22] Huang, X.; Huang, Q.; Lu, L., Construction of graphs with exactly k main eigenvalues, Linear Algebra Appl., 486, 204-218 (2015) · Zbl 1327.05208
[23] Ilić, A.; Stevanović, D., On comparing Zagreb indices, MATCH Commun. Math. Comput. Chem., 62, 681-687 (2009) · Zbl 1274.05095
[24] Rowlinson, P., The main eigenvalues of a graph: a survey, Appl. Anal. Discrete Math., 1, 445-471 (2007) · Zbl 1199.05241
[25] Shi, L., On graphs with given main eigenvalues, Appl. Math. Lett., 22, 1870-1874 (2009) · Zbl 1213.05172
[26] Stevanović, D., Spectral Radius of Graphs (2015), Academic Press: Academic Press Waltham · Zbl 1309.05001
[27] Tang, Z.; Hou, Y., The integral graphs with index 3 and exactly two main eigenvalues, Linear Algebra Appl., 433, 984-993 (2010) · Zbl 1215.05033
[28] Yu, A.; Lu, M.; Tian, F., On the spectral radius of graphs, Linear Algebra Appl., 387, 41-49 (2004) · Zbl 1041.05051
[29] Zhou, B., On spectral radius of nonnegative matrices, Australas. J. Comb., 22, 301-306 (2000) · Zbl 0981.05072
[30] Zhou, B., Zagreb indices, MATCH Commun. Math. Comput. Chem., 52, 113-118 (2004) · Zbl 1077.05519
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.