Using linear algebra The first branch of algebraic graph theory involves the study of graphs in connection with
linear algebra. Especially, it studies the
spectrum of the
adjacency matrix, or the
Laplacian matrix of a graph (this part of algebraic graph theory is also called
spectral graph theory). For the
Petersen graph, for example, the spectrum of the adjacency matrix is (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Several theorems relate properties of the spectrum to other
graph properties. As a simple example, a
connected graph with
diameter D will have at least
D+1 distinct values in its spectrum.
Aspects of graph spectra have been used in analysing the
synchronizability of
networks.
Using group theory The second branch of algebraic graph theory involves the study of graphs in connection to
group theory, particularly
automorphism groups and
geometric group theory. The focus is placed on various families of graphs based on
symmetry (such as
symmetric graphs,
vertex-transitive graphs,
edge-transitive graphs,
distance-transitive graphs,
distance-regular graphs, and
strongly regular graphs), and on the inclusion relationships between these families. Certain of such categories of graphs are sparse enough that
lists of graphs can be drawn up. By
Frucht's theorem, all
groups can be represented as the automorphism group of a connected graph (indeed, of a
cubic graph). Another connection with group theory is that, given any group, symmetrical graphs known as
Cayley graphs can be generated, and these have properties related to the structure of the group.
Studying graph invariants Finally, the third branch of algebraic graph theory concerns algebraic properties of
invariants of graphs, and especially the
chromatic polynomial, the
Tutte polynomial and
knot invariants. The chromatic polynomial of a graph, for example, counts the number of its proper
vertex colorings. For the Petersen graph, this polynomial is t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352). In particular, this means that the Petersen graph cannot be properly colored with one or two colors, but can be colored in 120 different ways with 3 colors. Much work in this area of algebraic graph theory was motivated by attempts to prove the
four color theorem. However, there are still many
open problems, such as characterizing graphs which have the same chromatic polynomial, and determining which polynomials are chromatic. ==See also==