JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 14, No 1 (2001)

D. Cvetković , P. Rowlinson² and S.K. Simić³

²Department of Computing Science and Mathematics, University of Stirling, Stirling FK9 4LA, Scotland S.K. SIMI Ć

Let G be a connected graph with least eigenvalue -2, of multiplicity k. A star complement for -2 in G is an induced subgraph H = G - X such that | X| = k and -2 is not an eigenvalue of H. In the case that G is a generalized line graph, a characterization of such subgraphs is used to decribe the eigenspace of -2. In some instances, G itself can be characterized by a star complement. If G is not a generalized line graph, G is an exceptional graph, and in this case it is shown how a star complement can be used to construct G without recourse to root systems.

1. F.K. Bell, “Characterizing line graphs by star complements,” Linear Algebra Appl. 296 (1999), 15-25.
2. F.K. Bell, D. Cvetković, P. Rowlinson, and S.K. Simić, “Some additions to the theory of star partitions of graphs,” Discussiones Mathematicae Graph Theory 19 (1999), 119-134.
3. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
4. F.C. Bussemaker and A. Neumaier, “Exceptional graphs with smallest eigenvalue - 2 and related problems,” Mathematics of Computation 59 (1992), 583-608.
5. P.J. Cameron, J.M. Goethals, J.J. Seidel, and E.E. Shult, “Line graphs, root systems, and elliptic geometry,” J. Algebra 43 (1976), 305-327.
6. P.J. Cameron and J.H. van Lint, Designs, Graphs, Codes and their Links, Cambridge University Press, Cambridge, 1991.
7. D. Cvetković, M. Doob, I. Gutman, and A. Torga\check sev, Recent Results in the Theory of Graph Spectra, North-Holland, Amsterdam, 1988.
8. D. Cvetković, M. Doob, and H. Sachs, Spectra of Graphs, 3rd edition, Johann Ambrosius Barth Verlag, Heidelberg, 1995.
9. D. Cvetković, M. Doob, and S. Simić, “Generalized line graphs,” J. Graph Theory 5 (1981), 385-399.
10. D. Cvetković, M. Lepović, P. Rowlinson, and S.K. Simić, “A database of star complements of graphs,” Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat. 9 (1998), 103-112.
11. D. Cvetković, M. Lepović, P. Rowlinson, and S.K. Simić, “The maximal exceptional graphs,” to appear.
12. D. Cvetković and M. Petrić, “A table of connected graphs on six vertices,” Discrete Math 50 (1984), 37-49.
13. D. Cvetković, P. Rowlinson, and S. Simić, “A study of eigenspaces of graphs,” Linear Algebra Appl. 182 (1993), 45-66.
14. D. Cvetković, P. Rowlinson, and S. Simić, Eigenspaces of Graphs, Cambridge University Press, Cambridge,
1997. CVETKOVI Ć, ROWLINSON AND SIMI Ć
15. D. Cvetković, P. Rowlinson, and S. Simić, “Some characterizations of graphs by star complements,” Linear Algebra Appl. 301 (1999), 81-97.
16. M. Doob, “An inter-relation between line graphs, eigenvalues and matroids,” J. Combinatorial Theory Ser. B 15 (1973), 40-50.
17. M. Doob and D. Cvetković, “On spectral characterizations and embeddings of graphs,” Linear Algebra Appl. 27 (1979), 17-26.
18. M.N. Ellingham, “Basic subgraphs and graph spectra,” Australasian J. Combinatorics 8 (1993), 247-265.
19. F.R. Gantmacher, The Theory of Matrices, Chelsea, New York, 1959.
20. P. Rowlinson, “Eutactic stars and graph spectra,” in Combinatorial and Graph-Thoeretical Problems in Linear Algebra, R.A. Brualdi, S. Friedland, and V. Klee (Eds.), Springer-Verlag, New York, 1993, pp. 153-164.
21. P. Rowlinson, “On graphs with multiple eigenvalues,” Linear Algebra and Appl. 283 (1998), 75-85.
22. P. Rowlinson, “Star sets and star complements in finite graphs: A spectral construction technique,” in Proc. Workshop in Discrete Mathematical Chemistry (March 1998), P. Hansen, P. Fowler, and M. Zheng (Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science 51 (2000), 323-332.
23. J.J. Seidel, “Eutactic stars,” in Combinatorics, A. Hajnal and V.T. Sós (Eds.), North-Holland, Amsterdam, 1978, pp. 983-999.