Eigenspaces of graphs

Authors Dragoš Cvetković, P. Rowlinson, Slobodan K. Simić

Publication date 24 February 1997

Published in Encyclopedia of Mathematics and Its Applications (Search for Journal in Brave)

Ever since it became known that the spectrum of a graph does not characterize it, research effort in spectral graph theory turned to the twin objectives of determining the structural properties of graphs that could be inferred from spectral properties and the discovery of further spectral invariants which together characterize graphs. Two earlier books on the subject ([\textit{D. M. Cvetković}, \textit{M. Doob}, and \textit{H. Sachs}, Spectra of graphs. Theory and applications. 3rd rev. a. enl. ed. (1995; Zbl 0824.05046)] and [\textit{D. M. Cvetković}, \textit{M. Dobb}, \textit{I. Gutman}, and \textit{A. Torgašev}, Recent results in the theory of graph spectra (1988; Zbl 0634.05054)]) covered the developments up to their time of publication. The present book, a sequel to these, reviews the earlier results and reports the discovery of a set of \(2m\) invariants (where \(m\) is the number of distinct eigenvalues) which completely determine a graph and discuss algorithms which compute these invariants, in polynomial time for many classes of graphs. We now describe the chapter contents:NEWLINENEWLINENEWLINEChapters 1 and 2 contain reviews of earlier results on eigenvalues and eigenvectors. Thus in Chapter 1 families of graphs characterized by spectral and other properties are discussed. These include line graphs of complete bipartite graphs, projective and affine planes, symmetric BIBDs and 2-designs, as also connected bipartite graphs, regular connected graphs and regular connected line graphs and cubic lattice graphs. Chapter 2 starts with the result that the number of components of a graph equals the maximum number of linearly independent eigenvectors. The concept of the main part of the spectrum is defined, as also the operation NEPS on \(n\) graphs which results in a graph whose vertex set is the Cartesian product of the vertex sets of the component graphs. The Sachs concept of the divisor of a graph is studied and it is shown that the spectrum of the divisor of a graph includes the main part of the spectrum of the graph. Applications to chessboard problems, coding theory, and switching in graphs are presented.NEWLINENEWLINENEWLINEChapter 3 introduces four eigenvector techniques to study the relation between graph spectra and graph structure. The Raleigh quotient gives a formula for the `index', the (largest eigenvalue) \(\mu\), and this is generalized to an arbitrary eigenvalue. Comparison of vectors (one of which is an eigenvector) is used to study the change in the index corresponding to elementary operations on graphs like splitting a vertex or subdividing an edge. Biquadratic forms are used to determine graphs with maximal index in a given family. The fourth technique of implicit functions involves the components of the principal eigenvector. A combination of these techniques helps one to determine the graphs with maximal or minimal index in several families of graphs.NEWLINENEWLINENEWLINEGraph angles are introduced in Chapter 4. The cosine of the angle made by the \(i\)th eigenspace with the \(j\)th coordinate axis is denoted by \(\alpha_{ij}\) and the \(m\times n\) matrix of these angles is called the angle matrix, where \(m\) is the number of eigenspaces and \(n\) is the number of vertices of the graph. It turns out that eigenvalues and angles do not characterize graphs: any two strongly regular graphs with the same parameters have the same eigenvalues and angles and there are non-isomorphic strongly regular graphs with same parameters. It is however reported that all graphs with up to 10 vertices are distinguished by eigenvalues and angles. All graphs with up to 5 vertices are listed in Appendix B, together with their eigenvalues, angles and main angles. (Main angles are cosines of the angles made by the eigenspaces with the all-1 vector J.) The behaviour of angles under several graph operations is studied. Another beautiful result is the wealth of information on the components of a graph provided by angles.NEWLINENEWLINENEWLINEChapter 5 deals with the construction of graphs with given eigenvalues and angles. It is observed that the family of cospectral trees studied by Schwenk to prove that almost all trees are cospectral are distinguished by angles. An algorithm to construct all trees with given eigenvalues and angles is given and is extended to the generation of all unicyclic graphs, bicyclic graphs, and a class of tree-like cubic graphs. For the general case, a necessary condition for an edge to exist and an edge to be a bridge are derived and used to obtain a fuzzy image of the graph. In the final subsection the authors argue that counterexamples to Ulam's conjecture should possibly be non-regular graphs with at most four eigenvalues which have the same angles and main angles.NEWLINENEWLINENEWLINEThe study of the changes in the index of a graph started in Chapter 4 is continued in Chapter 6 using the perturbation theory of matrices. In the analytic theory, the adjacency matrices of the initial and perturbed graphs are taken as \(A\) and \(A+B\), and considering any intermediate matrix as \(A+\zeta B\), expressions are obtained for the index and the principal eigenvector as power series in \(\zeta\). In the algebraic perturbation theory, taking \(\mathbb{R}^n\) with the standard inner product, the intermediate matrix is taken as \(\widetilde A+\widetilde BQ_r\), where \(Q_r\) is the orthogonal projection onto the subspace of \(\mathbb{R}^n\) spanned by the first \(r\) vectors of the standard basis of \(\mathbb{R}^n\). Perturbations considered include the elementary degree preserving transformation, addition, deletion, and relocation of an edge. Conditions under which the index increases or decreases are derived.NEWLINENEWLINENEWLINEStar partitions and star bases are defined in Chapter 7. A partition \(X_1\cup X_2\cup\cdots\cup X_m\) of the vertex set of a graph \(G\) is called a star partition if the vectors \(P_ie_j\) \((j\in X_i)\) form a basis for the eigenspace \(E(\mu_i)\), for each \(i\), \(1\leq i\leq m\), where the \(P_i\)'s are the orthogonal projections onto \(E(\mu_i)\) and \(\{e_j\}\) is the standard basis for \(\mathbb{R}^n\). The basis of \(\mathbb{R}^n\) made up by \(P_ie_j\), \(j\in X_i\), \(1\leq i\leq m\) is clled a star basis. It turns out that every graph has a star basis. The effect of graph operations on star partitions is studied as also the information on graph structure provided by the star partitions. If \((X_i)\) is a star partition of a graph \(G\) without isolated vertices, then \(V- X_i\) is a dominating set of \(G\), and if \(G- X_i\) has no isolated vertices, then the set of all vertices between \(X_i\) and \(V- X_i\) is a perfect matching for \(G\). The authors then discuss the enumeration of all star partitions and all non-isomorphic star partitions of a graph. A complete analysis is given for the Petersen graph. The problem of computing the eigenvectors is studied at some length.NEWLINENEWLINENEWLINEThe most important result reported in Chapter 8 is the discovery of a canonical star basis for any graph. This is based on a canonical graph ordering (CGO) and a canonical vertex ordering (CVO), which are defined recursively through a process requiring several optimizations. The final output is a unique canonical star basis \(S=(S_1,S_2,\dots, S_m)\) for a graph where the columns of \(S_i\) form a star basis for the \(i\)th eigenspace. The \(2m\) parameters \(\mu_1,\mu_2,\dots,\mu_m\) and \(S_1,S_2,\dots, S_m\) form a complete set of graph invariants. Two algorithms are described to find a star basis for a graph, of complexity \(O(n^4)\) and \(O(n^5)\) respectively. The problem of finding a canonical basis for a general graph is shown to depend on several instances of finding a maximal clique in a weighted graph. If the eigenvalues are bounded, this reduces to a polynomial algorithm. For a graph without repeated eigenvalues a polynomial time algorithm is described, based on finding a perfect matching in a weighted bipartite graph. For the strongly regular graphs the problem reduces to finding a minimum cut in a graph. Research on this topic is reported to be in progress.NEWLINENEWLINENEWLINEChapter 9 is devoted to some miscellaneous results not classifiable into the earlier chapters. These include upper bounds for the number of components in a subgraph induced by a vertex subset of the graph, an upper bound for the second largest eigenvalue, an application to quantum chemistry, and a decomposition of \(K_n\) into edge-disjoint spanning subgraphs each isomorphic to the same given strongly regular graph.NEWLINENEWLINENEWLINEThis book will be a valuable addition to the reference library of every serious graph theorist. There are a few obvious misprints which can be easily corrected.

Recommendations

Cited in

(only showing first 100 items - show all)

This page was built for publication: Eigenspaces of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2785496)