Branches of algebraic graph theory Algebraic graph theory

1 branches of algebraic graph theory

1.1 using linear algebra
1.2 using group theory
1.3 studying graph invariants

branches of algebraic graph theory
using linear algebra

the first branch of algebraic graph theory involves study of graphs in connection linear algebra. especially, studies spectrum of adjacency matrix, or laplacian matrix of graph (this part of algebraic graph theory called spectral graph theory). petersen graph, example, spectrum of adjacency matrix (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). several theorems relate properties of spectrum other graph properties. simple example, connected graph diameter d have @ least d+1 distinct values in spectrum. aspects of graph spectra have been used in analysing synchronizability of networks.

using group theory

the second branch of algebraic graph theory involves study of graphs in connection group theory, particularly automorphism groups , geometric group theory. focus placed on various families of graphs based on symmetry (such symmetric graphs, vertex-transitive graphs, edge-transitive graphs, distance-transitive graphs, distance-regular graphs, , regular graphs), , on inclusion relationships between these families. of such categories of graphs sparse enough lists of graphs can drawn up. frucht s theorem, groups can represented automorphism group of connected graph (indeed, of cubic graph). connection group theory that, given group, symmetrical graphs known cayley graphs can generated, , these have properties related structure of group.

a cayley graph alternating group a4, forming truncated tetrahedron in 3 dimensions. cayley graphs vertex-transitive, vertex-transitive graphs (like petersen graph) not cayley graphs.



a proper vertex coloring of petersen graph 3 colors, minimum number possible. according chromatic polynomial, there 120 such colorings 3 colors.

this second branch of algebraic graph theory related first, since symmetry properties of graph reflected in spectrum. in particular, spectrum of highly symmetrical graph, such petersen graph, has few distinct values (the petersen graph has 3, minimum possible, given diameter). cayley graphs, spectrum can related directly structure of group, in particular irreducible characters.

studying graph invariants

finally, third branch of algebraic graph theory concerns algebraic properties of invariants of graphs, , chromatic polynomial, tutte polynomial , knot invariants. chromatic polynomial of graph, example, counts number of proper vertex colorings. petersen graph, polynomial



t
(
t
−
1
)
(
t
−
2
)
(

t

7


−
12

t

6


+
67

t

5


−
230

t

4


+
529

t

3


−
814

t

2


+
775
t
−
352
)


{\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}

. in particular, means petersen graph cannot colored 1 or 2 colors, can colored in 120 different ways 3 colors. work in area of algebraic graph theory motivated attempts prove 4 color theorem. however, there still many open problems, such characterizing graphs have same chromatic polynomial, , determining polynomials chromatic.