Graph Symmetry

Group Formulation §

• We can consider a permutation group acting on the vertices of graph .

• See more in Graph Homomorphism

• (Godsil e2.8) Let be self-complementary with more than one vertex. Then there exists a permutation of such that

  • .

    • Proof: Because , we can map edges as follows in a bijective manner for any . is precisely the bijection mapping , and so on.

  • where

    • Proof: Consider , which maps , and the transposition that swaps and . In particular, choose such that . Clearly but also .

      To show . Consider . If we are done. Otherwise then . but clearly so .

  • The orbits of on induce self-complementary subgraphs of

    • Proof: Consider the isomorphism which maps where and and where and . is a permutation which can be decomposed into cycles. Each cycle corresponds to an orbit.

      Let be a cycle. The restriction on this cycle is clearly self-complementary based on how we defined .

• (Godsil e2.13) Let be a graph such that acts transitively on and be a block of imprimitivity for , then is regular.

  • Proof To show is regular, note that is an automorphism acting transitively on . Because is a block of imprimitivity, either or . In the first case If then so is . In the second, if then . Importantly, this means that in either case the degree is preserved in the mapping since we do not connect to vertices outside of the block’s image.

    Because it is always possible to find such that , we can map edges with as one end point to edges with as one end point (i.e., ). They share the same degree, and because they were arbitrarily chosen, all vertices of share the same degree. Hence is regular.

Spectral Formulation §

• (Mesbahi 2.19) Let be the adjacency matrix of the graph and a permutation on its vertex set . Associate the permutation with a permutation matrix such that

  Then is an automorphism of if and only if

  The order of an automorphism is defined as the least positive integer for which

• (Mesbahi 2.20) If all eigenvalues of the adjacency matrix of the graph are simple, then every non-identity automorphism of has order two.

Quotient Objects §

• A cell is a subset of the vertex set . A partition of is a grouping of a vertex set into different cells. A nontrivial cell is a cell containing more than one vertex.

  • A characteristic vector of a nontrivial cell has -s in its components associated with and s elsewhere.
  • The characteristic matrix is a matrix with characteristic vectors as columns.

• An -partition of with cells is equitable if each vertex in has the same number of neighbors in for all .

  The cardinality of a partition is denoted .

• The quotient of over is defined as the digraph, potentially with cell loops where the cells are the nodes and are edges. [^quotient]

  • The adjacency matrix of the quotient is specified by

• A non-trivial equitable partition contains at least one cell with more than one node.

• (Mesbahi 2.23) Let be the characteristic matrix of an equitable partition of . Then

  And

  (See Matrix Pseudo-Inverse)

• (Mesbahi 2.24) Let be a partition of with characteristic matrix . Then is equitable if and only if the column space of is -invariant.

  That is

Links §

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