Algebraic Graph Theory

• An extension of Graph Theory that combines insights from Linear Algebra, Group Theory, and Ring Theory.

Results §

• (Mesbahi 2.7) Given a weakly connected digraph , the null space of is spanned by all linearly independent signed path vectors corresponding to the cycles of .
  • The cycle space of a digraph is defined as , that is the null space of the associated incidence matrix.
  • The cut space of a digraph is defined as , that is the orthogonal complement of the cycle space.

Topics §

• Matrices in Graph Theory - could be seen as fundamental objects in Algebraic Graph Theory.

• Graph Laplacian

• Graph Symmetry

• Chegeer’s Inequality

• Spectral Convolution

• Algebraic Graph Theory — Notation Guide

Links §

• Graph Theoretic Methods in Multiagent Networks by Mesbahi and Egerstedt
• Algebraic Graph Theory by Godsil and Royle