Algebraic graph theory

From Wikipedia, the free encyclopedia

Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs.

In one sense, algebraic graph theory studies graphs in connection with linear algebra. Especially, it studies the spectrum of the adjacency matrix, the Kirchhoff matrix, or the Laplacian matrix of a graph. This part of algebraic graph theory is also called spectral graph theory.

In another sense, algebraic graph theory studies graphs in connection to group theory, particularly automorphism groups and geometric group theory. In the latter, the endomorphism monoid of a graph plays an important role. The focus is placed on various families of symmetric graphs, such as vertex-transitive graphs, edge-transitive graphs, arc-transitive graphs, distance-transitive graphs, Cayley graphs, etc.

The two senses overlap in the study of distance-regular and strongly regular graphs, where nontrivial automorphisms may not exist but numerical regularities, which occur when the automorphism group is large and sometimes also when it is small, make it possible to apply matrix methods. These kinds of graphs lead to association schemes, whose methods form a third part of algebraic graph theory (not always distinguishable from the first sense).

Finally, a branch of algebraic graph theory concerns algebraic properties of invariants of graphs, and especially the Tutte polynomial and knot invariants.