Algebraic graph theory

This is in contrast to geometric, combinatoric, or algorithmic approaches.

There are three main branches of algebraic graph theory, involving the use of linear algebra, the use of group theory, and the study of graph invariants.

As a simple example, a connected graph with diameter D will have at least D+1 distinct values in its spectrum.

[1] Aspects of graph spectra have been used in analysing the synchronizability of networks.

For Cayley graphs, the spectrum can be related directly to the structure of the group, in particular to its irreducible characters.

[1][3] 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.

Much work in this area of algebraic graph theory was motivated by attempts to prove the four color theorem.

A highly symmetrical graph, the Petersen graph , which is vertex-transitive , symmetric , distance-transitive , and distance-regular . It has diameter 2. Its automorphism group has 120 elements, and is in fact the symmetric group .
A Cayley graph for the alternating group A 4 , forming a truncated tetrahedron in three dimensions. All Cayley graphs are vertex-transitive , but some vertex-transitive graphs (like the Petersen graph ) are not Cayley graphs.
A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. According to the chromatic polynomial , there are 120 such colorings with 3 colors.