×

Connected graphs of fixed order and size with maximal index: some spectral bounds. (English) Zbl 1217.05157

Summary: The index (or spectral radius) of a simple graph is the largest eigenvalue of its adjacency matrix. For connected graphs of fixed order and size the graphs with maximal index are not yet identified (in the general case). It is known (for a long time) that these graphs are nested split graphs (or threshold graphs). In this paper we use the eigenvector techniques for getting some new (lower and upper) bounds on the index of nested split graphs. Besides we give some computational results in order to compare these bounds.

MSC:

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

References:

[1] Aouchiche, M.; Bell, F. K.; Cvetković, D.; Hansen, P.; Rowlinson, P.; Simić, S. K.; Stevanović, D., Variable neighborhood search for extremal graphs, 16. Some conjectures related to the largest eigenvalue of a graph, Eur. J. Oper. Res., 191, 3, 661-676 (2008) · Zbl 1160.90494
[2] Brualdi, R. A.; Hoffman, A. J., On the spectral radius of \((0, 1)\) matrices, Linear Algebra Appl., 65, 133-146 (1985) · Zbl 0563.15012
[3] Brualdi, R. A.; Solheid, E. S., On the spectral radius of connected graphs, Publ. Inst. Math. (Beograd), 39, 53, 45-54 (1986) · Zbl 0603.05028
[4] D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs - Theory and Applications, third revised and enlarged ed., Johan Ambrosius Bart. Verlag, Heidelberg-Leipzig, 1995.; D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs - Theory and Applications, third revised and enlarged ed., Johan Ambrosius Bart. Verlag, Heidelberg-Leipzig, 1995.
[5] Cvetković, D.; Rowlinson, P., On connected graphs with maximal index, Publ. Inst. Math. (Beograd), 44, 58, 29-34 (1988) · Zbl 0661.05041
[6] Cvetković, D.; Rowlinson, P., The largest eigenvalue of a graph: a survey, Linear and Multilinear Algebra, 28, 3-33 (1990) · Zbl 0744.05031
[7] Cvetković, D.; Rowlinson, P.; Simić, S., Eigenspaces of Graphs (1997), Cambridge University Press · Zbl 0878.05057
[8] Friedland, S., The maximal eigenvalue of \(0 - 1\) matrices with prescribed number of ones, Linear Algebra Appl., 69, 33-69 (1985) · Zbl 0578.15010
[9] Friedland, S., Bounds on the spectral radius of graphs with \(e\) edges, Linear Algebra Appl., 101, 81-86 (1988) · Zbl 0658.05054
[10] Rowlinson, P., On the maximal index of graphs with a prescribed number of edges, Linear Algebra Appl., 110, 43-53 (1988) · Zbl 0666.05043
[11] S.K. Simić, E.M. Li Marzi, F. Belardo, Connected graphs of fixed order and size with maximal index: structural considerations, Le Matematiche, Vol. LIX(2004)-Fasc. I-II, pp. 349-365.; S.K. Simić, E.M. Li Marzi, F. Belardo, Connected graphs of fixed order and size with maximal index: structural considerations, Le Matematiche, Vol. LIX(2004)-Fasc. I-II, pp. 349-365. · Zbl 1195.05045
[12] Stanley, R. P., A bound on the spectral radius of graphs with \(e\) edges, Linear Algebra Appl., 87, 267-269 (1987) · Zbl 0617.05045
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.