In graph theory, a branch of mathematics, an equitable partition of the vertex set V of a graph G = (V, E) is a partition of V such that, for any pair of vertices u and v in the same set of the partition and any set B of the partition, both u and v have the same number of neighbors in B.
More precisely, one represents where every vertex is contained in exactly one "cell" , the edges within each cell form a regular graph, and for any two distinct cells and and every vertex , the number of edges such that is a constant , independent of the choice of .
The characteristic matrix of the partition has a row for each vertex and a column for each cell, with 1 in row and column if , otherwise 0.
The orbits of a group of automorphisms of G form an equitable partition of V. This fact can assist in studying eigenvalues of graphs with vertex-transitive automorphism group. It can also assist in determining isomorphism of graphs.
Equitable partitions allow collapsing graphical matrices into smaller, matrices while preserving the set of eigenvalues. Thus, they can facilitate spectral graph theory. For example, if is an equitable partition of , then the characteristic polynomial of is divisible by that of , where is a weighted directed graph formed by collapsing each cell to a single vertex. Thus, the eigenvalues of are also eigenvalues of , but may be a much smaller matrix so easier to compute with.
This is especially relevant to distance regular graphs, where the partition based on distance from a chosen vertex is equitable. That makes for, besides simplified computation of eigenvalues, a simple diagram of the numerical properties of a distance regular graph.