×

The maximal exceptional graphs. (English) Zbl 1028.05063

An exceptional graph is a connected graph with least eigenvalue greater than or equal to \(-2\) which is not a generalized line graph. Such graphs are known to be representable in the exceptional root system \(\mathbb{E}_8\). An exceptional graph is said to be maximal if it is no induced subgraph of another exceptional graph. We note that every exceptional graph is an induced subgraph of some maximal exceptional graph.
In this paper all maximal exceptional graphs are determined by a computer search using the star complement technique, and then it is shown how they can be found by theoretical consideration using a representation of \(\mathbb{E}_8\) in \(\mathbb{R}^8\). There are exactly 473 maximal exceptional graphs.

MSC:

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

References:

[1] Bridges, W. G.; Mena, R. A., Multiplicative cones—a family of three-eigenvalue graphs, Aequationes Math., 22, 208-214 (1981) · Zbl 0481.05043
[2] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs (1989), Springer-Verlag: Springer-Verlag Berlin · Zbl 0747.05073
[3] F. C. Bussemaker, D. Cvetković, and, J. J. Seidel, Graphs Related to Exceptional Root Systems, T.H.-Report, 76-WSK-05, Eindhoven, 1976.; F. C. Bussemaker, D. Cvetković, and, J. J. Seidel, Graphs Related to Exceptional Root Systems, T.H.-Report, 76-WSK-05, Eindhoven, 1976.
[4] Bussemaker, F. C.; Cvetković, D.; Seidel, J. J., Graphs related to exceptional root systems, (Hajnal, A.; Sós, V. T., Combinatorics (1978), North-Holland: North-Holland Amsterdam), 185-191 · Zbl 0392.05055
[5] Bussemaker, F. C.; Neumaier, A., Exceptional graphs with smallest eigenvalue −2 and related problems, Mathe. Comput., 59, 583-608 (1992) · Zbl 0770.05060
[6] Cameron, P. J.; Goethals, J. M.; Seidel, J. J.; Shult, E. E., Line graphs, root systems, and elliptic geometry, J. Algebra, 43, 305-327 (1976) · Zbl 0337.05142
[7] Cameron, P. J.; van Lint, J. H., Designs, Graphs, Codes and their Links (1991), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0743.05004
[8] Cvetković, D.; Doob, M.; Gutman, I.; Torgašev, A., Recent Results in the Theory of Graph Spectra (1988), North-Holland: North-Holland Amsterdam · Zbl 0634.05054
[9] Cvetković, D.; Doob, M.; Sachs, H., Spectra of Graphs (1995), Johann Ambrosius Barth Verlag: Johann Ambrosius Barth Verlag Heidelberg · Zbl 0824.05046
[10] Cvetković, D.; Doob, M.; Simić, S., Generalized line graphs, J. Graph Theory, 5, 385-399 (1981) · Zbl 0475.05061
[11] Cvetković, D.; Lepović, M.; Rowlinson, P.; Simić, S., A database of star complements of graphs, Univ. Beograd, Publ. Elektrotehn. Fak. Ser. Mat., 9, 103-112 (1998) · Zbl 1008.05095
[12] D. Cvetković, M. Lepović, P. Rowlinson, and, S. Simić, Computer Investigations of the Maximal Exceptional Graphs, Technical Report, CSM-160, Department of Computing Science and Mathematics, University of Stirling, 2001.; D. Cvetković, M. Lepović, P. Rowlinson, and, S. Simić, Computer Investigations of the Maximal Exceptional Graphs, Technical Report, CSM-160, Department of Computing Science and Mathematics, University of Stirling, 2001.
[13] Cvetković, D.; Petrić, M., A table of connected graphs on six vertices, Discrete Math., 50, 37-49 (1984) · Zbl 0533.05052
[14] Cvetković, D.; Rowlinson, P.; Simić, S. K., Eigenspaces of Graphs (1997), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0878.05057
[15] Cvetković, D.; Rowlinson, P.; Simić, S. K., Some characterizations of graphs by star complements, Linear Algebra Appl., 301, 81-97 (1999) · Zbl 0945.05042
[16] Cvetković, D.; Rowlinson, P.; Simić, S. K., Graphs with least eigenvalue −2: The star complement technique, J. Algebraic Combin., 14, 5-16 (2001) · Zbl 0982.05065
[17] Cvetković, D.; Rowlinson, P.; Simić, S. K., The maximal exceptional graphs with maximal degree less than 28, Bull. Serb. Acad. Sci. Arts, Cl. Sci. Math. Natur., Sci. Math., 22, 115-131 (2001) · Zbl 0997.05060
[18] van Dam, E. R., Nonregular graphs with three eigenvalues, J. Combin. Theory Ser. B, 73, 101-118 (1998) · Zbl 0917.05044
[19] Deleted in proof.; Deleted in proof.
[20] Doob, M.; Cvetković, D., On spectral characterizations and embeddings of graphs, Linear Algebra Appl., 27, 17-26 (1979) · Zbl 0417.05025
[21] Ellingham, M. N., Basic subgraphs and graph spectra, Australasian J. Combin., 8, 247-265 (1993) · Zbl 0790.05057
[22] Rowlinson, P., On graphs with multiple eigenvalues, Linear Algebra Appl., 283, 75-85 (1998) · Zbl 0931.05055
[23] Rowlinson, P., Star sets and star complements in finite graphs—A spectral construction technique, (DIMACS Workshop, March 1998; Hansen, P.; Fowler, P.; Zheng, M., Discrete Mathematical Chemistry, 51 (2000), American Mathematical Society: American Mathematical Society Providence), 323-332 · Zbl 0964.05041
[24] J. J. Seidel, On Two-Graphs and Shult’s Characterization of Symplectic and Orthogonal Geometries Over GF(2), T.H.-Report, 73-WSK-02, Eindhoven, 1973.; J. J. Seidel, On Two-Graphs and Shult’s Characterization of Symplectic and Orthogonal Geometries Over GF(2), T.H.-Report, 73-WSK-02, Eindhoven, 1973. · Zbl 0273.05130
[25] Seidel, J. J., Eutactic stars, (Hajnal, A.; Sós, V. T., Combinatorics (1978), North-Holland: North-Holland Amsterdam), 983-989 · Zbl 0391.05050
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.