×

On graphs with multiple eigenvalues. (English) Zbl 0931.05055

Summary: Let \({\mathcal E}(\mu)\) be an eigenspace of a finite graph \(G\), with dimension \(m\) and codimension \(t>1\). It is shown that if \(\mu\notin\{-1,0\}\) then \(m\leq{1\over 2}(t-1)(t+ 4)\). A necessary and sufficient condition for \(\mu\) to be a multiple eigenvalue of \(G\) is established, and used to construct examples from intersecting families of sets.

MSC:

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

References:

[1] Rowlinson, P., Eutactic stars and graph spectra, (Brualdi, R. A.; Friedland, S.; Klee, V., Combinatorial and Graph-Theoretic Problems in Linear Algebra (1993), Springer: Springer New York), 153-164 · Zbl 0789.05066
[2] Cvetković, D.; Rowlinson, P.; Simić, S., Eigenspaces of Graphs (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0878.05057
[3] Ellingham, M. N., Basic subgraphs and graph spectra, Australasian J. Combinatorics, 8, 247-265 (1993) · Zbl 0790.05057
[4] Rowlinson, P., Star partitions and regularity in graphs, Linear Algebra Appl., 226-228, 247-265 (1995) · Zbl 0846.05058
[5] Seidel, J. J., Geometric representations of graphs, Linear and Multilinear Algebra, 39, 45-57 (1995) · Zbl 0832.05079
[6] Cvetković, D.; Doob, M.; Sachs, H., Spectra of Graphs (1995), Johann Ambrosius Barth Verlag: Johann Ambrosius Barth Verlag Heidelberg · Zbl 0824.05046
[7] van Dam, E. R., Graphs with Few Eigenvalues, Center for Economic Research, Tilburg University, Dissertation Series, No. 20 (1996)
[8] Beth, T.; Jungnickel, D.; Lenz, H., Design Theory (1993), Cambridge University Press: Cambridge University Press Cambridge
[9] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs (1989), Springer: Springer Heidelberg · Zbl 0747.05073
[10] Cameron, P. J.; van Lint, J. H., Designs, Graphs, Codes and their Links (1991), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0743.05004
[11] Witt, E., Über Steinischer Systeme, Abh. Math. Sem. Hamburg, 12, 265-275 (1938) · JFM 64.0937.02
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.