An automorphism of a graph is a permutation of its vertex such that

An automorphism group is defined as the set of all graph automorphisms on .
(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

The Library