×
Aouchiche, Mustapha; Hansen, Pierre; Lucas, Claire

On the extremal values of the second largest \(Q\)-eigenvalue. (English) Zbl 1222.05146

Linear Algebra Appl. 435, No. 10, 2591-2606 (2011).
Summary: We study extremal graphs for the extremal values of the second largest \(Q\)-eigenvalue of a connected graph. We first characterize all simple connected graphs with second largest signless Laplacian eigenvalue at most 3. The second part of the present paper is devoted to the study of the graphs that maximize the second largest \(Q\)-eigenvalue. We construct families of such graphs and prove that some of theses families are minimal for the fact that they maximize the second largest signless Laplacian eigenvalue.

Cited in 1 Review
Cited in 19 Documents

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C35 Extremal problems in graph theory

Keywords:

signless Laplacian; second largest eigenvalue; critical graph; extremal graph

Software:

AutoGraphiX
Cite Review PDF
Full Text: DOI

References:

[1] Aouchiche, M.; Bonnefoy, J.-M.; Fidahoussen, A.; Caporossi, G.; Hansen, P.; Hiesse, L.; Lacheré, J.; Monhait, A., Variable neighborhood search for extremal graphs. 14: The AutoGraphiX 2 system, (Liberti, L.; Maculan, N., Global Optimization: From Theory to Implementation (2006), Springer), 281-310 · Zbl 1100.90052
[2] Aouchiche, M.; Caporossi, G.; Hansen, P., Variable neighborhood search for extremal graphs. 20: Automated comparison of graph invariants, Match, 58, 365-384 (2007) · Zbl 1274.05235
[3] Caporossi, G.; Hansen, P., Variable neighborhood search for extremal graphs. I: The AutoGraphiX system, Discrete Math., 212, 29-44 (2000) · Zbl 0947.90130
[4] Caporossi, G.; Hansen, P., Variable neighborhood search for extremal graphs. 5: Three ways to automate finding conjectures, Discrete Math., 276, 81-94 (2004) · Zbl 1031.05068
[5] Cardoso, D. M.; Cvetković, D.; Rowlinson, P.; Simić, S. K., A sharp lower bound for the least eigenvalue of the signless Laplacian of a non-bipartite graph, Linear Algebra Appl., 429, 2770-2780 (2008) · Zbl 1148.05046
[6] Chen, Y., Properties of spectra of graphs and line graphs, Appl. Math. J. Chinese Univ. Ser. B, 17, 371-376 (2002) · Zbl 1022.05046
[7] F.R.K. Chung, Spectral Graph Theory, in: Amer. Math. Soc., Providence Rhode Island, 1997.; F.R.K. Chung, Spectral Graph Theory, in: Amer. Math. Soc., Providence Rhode Island, 1997.
[8] Cvetković, D., New theorems for the signless Laplacian eigenvalues, Bull. Sci. Math. Nat. Acad. Sci. Bucarest, 137, 33, 131-146 (2008) · Zbl 1199.05212
[9] Cvetković, D., On graphs whose second largest eigenvalue does not exceed 1, Publ. Inst. Math. (Beograd) (N.S.), 31, 45, 15-20 (1982) · Zbl 0522.05044
[10] Cvetkovć, D.; Doob, M.; Sachs, H., Spectra of Graphs - Theory and Application (1982), Academic Press: Academic Press New York
[11] Cvetković, D.; Rowlinson, P.; Simić, S. K., Signless Laplacians of finite graphs, Linear Algebra Appl., 423, 155-171 (2007) · Zbl 1113.05061
[12] Cvetković, D.; Rowlinson, P.; Simić, S. K., Eigenvalue bounds for the signless Laplacian, Publ. Inst. Math. (Beograd) (N.S.), 81, 95, 11-27 (2007) · Zbl 1164.05038
[13] Cvetković, D.; Simić, S. K., Towards a spectral theory of graphs based on the signless Laplacian. I, Publ. Inst. Math. (Beograd) (N.S.), 85, 99, 19-33 (2009) · Zbl 1224.05293
[14] Cvetković, D.; Simić, S. K., Towards a spectral theory of graphs based on the signless Laplacian. II, Linear Algebra Appl., 432, 2257-2272 (2010) · Zbl 1218.05089
[15] Cvetković, D.; Simić, S. K., Towards a spectral theory of graphs based on the signless laplacian. III, Appl. Anal. Discrete Math., 4, 156-166 (2010) · Zbl 1265.05360
[16] Cvetković, D.; Simić, S. K., On graphs whose second largest eigenvalue does not exceed \((\sqrt{5} - 1) / 2\), Discrete Math., 138, 213-227 (1995) · Zbl 0842.05059
[17] Das, K. C., on conjectures involving second largest signless Laplacian eigenvalue of graphs, Linear Algebra Appl., 432, 3018-3029 (2010) · Zbl 1195.05040
[18] Feng, L.; Yu, G., On conjectures involving second largest signless Laplacian eigenvalue of graphs, Publ. Inst. Math. (Beograd) (N.S.), 85, 99, 35-38 (2009) · Zbl 1265.05365
[19] Guo, S. G., On bicyclic graphs whose second largest eigenvalue does not exceed 1, Linear Algebra Appl., 407, 201-210 (2005) · Zbl 1073.05043
[20] Merris, R., A note on Laplacian graph eigenvalues, Linear Algebra Appl., 285, 33-35 (1998) · Zbl 0931.05053
[21] Oliveira, C. S.; Lima, L. S.; de Abreu, N. M.M.; Hansen, P., Bounds on the index of the signless Laplacian of a graph, Discrete Appl. Math., 158, 355-360 (2010) · Zbl 1225.05174
[22] Petrović, M.; Milekić, B., On the second largest eigenvalue of line graphs, J. Graph Theory, 27, 61-66 (1998) · Zbl 0892.05031
[23] J.R. Schott, Matrix Analysis for Statistics, second ed., in: Wiley Series in Probability and Statistics, Wiley-Interscience (John Wiley & Sons), Hoboken, NJ, 2005.; J.R. Schott, Matrix Analysis for Statistics, second ed., in: Wiley Series in Probability and Statistics, Wiley-Interscience (John Wiley & Sons), Hoboken, NJ, 2005. · Zbl 1076.15002
[24] Wang, J.; Belardo, F.; Huang, Q.; Borovićanin, B., On the two largest Q-eigenvalues of graphs, Discrete Math., 310, 2858-2866 (2010) · Zbl 1208.05079
[25] Xu, G. H., On unicyclic graphs whose second largest eigenvalue does not exceed 1, Discrete Appl. Math., 136, 117-124 (2004) · Zbl 1032.05085
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.