×

On the two largest \(Q\)-eigenvalues of graphs. (English) Zbl 1208.05079

Summary: We first give an upper bound for the largest signless Laplacian eigenvalue of a graph and find all the extremal graphs. Secondly, we consider the second-largest signless Laplacian eigenvalue and we characterize the connected graphs whose second-largest signless Laplacian eigenvalue does not exceed 3. Furthermore, we give the signless Laplacian spectral characterization of the latter graphs. In particular, the well-known friendship graph is proved to be determined by the signless Laplacian spectrum.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brigham, R. C.; Dutton, R. D., Bounds on graphs spectra, J. Combin. Theory Ser. B, 37, 228-234 (1984) · Zbl 0537.05041
[2] Cvetković, D., New theorems for signless Laplacian eigenvalues, Bull. Acad. Serbe Sci. Arts Cl. Sci. Math. Natur. Sci. Math., 137, 33, 131-146 (2008) · Zbl 1199.05212
[3] Cvetković, D.; Doob, M.; Sachs, H., Spectra of Graphs—Theory and Applications (1995), Johan Ambrosius Bart Verlag: Johan Ambrosius Bart Verlag Heidelberg, Leipzig · Zbl 0824.05046
[4] Cvetković, D.; Rowlinson, P.; Simić, S. K., Eigenvalue bounds for the signless Laplacians, Publ. Inst. Math. (Beograd) (NS), 81, 95, 11-27 (2007) · Zbl 1164.05038
[5] Cvetković, D.; Rowlinson, P.; Simić, S. K., Signless Laplacian of finite graphs, Linear Algebra Appl., 423, 155-171 (2007) · Zbl 1113.05061
[6] Cvetković, D.; Simić, S. K., Towards a spectral theory of graphs based on signless Laplacian, I, Publ. Inst. Math. (Beograd) (NS), 85, 99, 19-33 (2009) · Zbl 1224.05293
[7] Cvetković, D.; Simić, S. K., Towards a spectral theory of graphs based on signless Laplacian, II, Linear Algebra Appl., 432, 2257-2272 (2010) · Zbl 1218.05089
[8] Cvetković, D.; Simić, S. K., Towards a spectral theory of graphs based on signless Laplacian, III, Appl. Anal. Discrete Math., 4, 156-166 (2010) · Zbl 1265.05360
[9] Ellingham, M. N.; Zha, X., The spectral radius of graphs on surface, J. Combin. Theory Ser. B, 78, 45-56 (2000) · Zbl 1028.05065
[10] Erdös, P.; Rényi, A.; Sós, V., On a problem of graph theory, Studia Sci. Math., 1, 215-235 (1966) · Zbl 0144.23302
[11] Günthard, Hs. H.; Primas, H., Zusammenhang von Graphtheorie und Mo-Theotie von Molekeln mit systemen konjugierter Bindungen, Helv. Chim. Acta, 39, 1645-1653 (1956)
[12] Hong, Y.; Shu, J. L.; Fang, K., A sharp upper bound of the spectral radius of graphs, J. Combin. Theory Ser. B, 81, 177-183 (2001) · Zbl 1024.05059
[13] Liu, X.; Zhang, Y.; Gui, X., The multi-fan graphs are determined by their Laplacian spectra, Discrete Math., 308, 4267-4271 (2008) · Zbl 1225.05172
[14] Oliveira, C. S.; de Lima, L. S.; de Abreu, N. M.M.; Kirkland, S., Bounds on the \(Q\)-spread of a graph, Linear Algebra Appl., 432, 2342-2351 (2010) · Zbl 1214.05082
[15] Omidi, G. R., On a signless Laplacian spectral characterization of \(T\)-shape trees, Linear Algebra Appl., 431, 1607-1615 (2009) · Zbl 1169.05351
[16] Petrović, M.; Milekić, B., On the second largest eigenvalue of line graphs, J. Graph Theory, 27, 61-66 (1998) · Zbl 0892.05031
[17] Powers, D. L., Graphs partitioning by eigenvectors, Linear Algebra Appl., 101, 121-133 (1988) · Zbl 0666.05056
[18] Smith, J. H., Some properties of the spectrum of a graph, (Guy, R.; etal., Combinatorial Structures and their Applications. Combinatorial Structures and their Applications, Proc. Conf. Calgary, 1969 (1970), Gordon and Breach: Gordon and Breach New York), 403-406
[19] van Dam, E. R.; Haemers, W. H., Which graphs are determined by their spectra?, Linear Algebra Appl., 373, 241-272 (2003) · Zbl 1026.05079
[20] van Dam, E. R.; Haemers, W. H., Developments on spectral characterizations of graphs, Discrete Math., 309, 576-586 (2009) · Zbl 1205.05156
[21] Wang, J. F.; Huang, Q. X.; Belardo, F.; Li Marzi, E. M., On graphs whose signless Laplacian index does not exceed 4.5, Linear Algebra Appl., 431, 162-178 (2009) · Zbl 1171.05035
[22] Wang, J. F.; Huang, Q. X.; Belardo, F.; Li Marzi, E. M., On the spectral characterizations of \(\infty \)-graphs, Discrete Math., 310, 1845-1855 (2010) · Zbl 1231.05174
[23] Wilf, H., (Welsh, D. J.A., The Friendship Theorem, Combinatorial Mathematics and its Applications (1971), Academic Press: Academic Press New York, London), 307-309
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.