Algebraic graph theory

Algebraic graph theory — алгебраическая теория графов.

Algebraic graph theory can be considered as a branch of the graph theory, where eigenvalues and eigenvectors of certain matrices associated with graphs are employed to deduce some of their properties. In fact, eigenvalues are closely related to almost all major invariants of a graph, linking one extremal property to another. These eigenvalues play a central role in our fundamental understanding of graphs. Many interesting books on the algebraic graph theory can be found, such as Biggs (1993), Cvetkovic et al. (1980), Seidel (1989), and Chung (1997).

One of the major contributions to the algebraic graph theory is due to Fiedler, where the properties of the second eigenvalue and eigenvector of the Laplacian of a graph have been introduced. This eigenvector, known as the Fiedler vector, is used in graph partitioning and nodal ordering.