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.
Equitable partitions are important for simplifying calculations involving adjacency and related matrices of large graphs.
Equitable partitions from automorphisms
The orbits of a group of automorphisms of G form an equitable partition of V.Godsil and Royle (2001), Section 9.3. This fact can assist in studying eigenvalues of graphs with vertex-transitive automorphism group. It can also assist in determining isomorphism of graphs.McKay (1981).
Matrix use
Equitable partitions allow collapsing graphical matrices into smaller, matrices while preserving the set of eigenvalues. Thus, they can facilitate spectral graph theory.Godsil and Royle (2001), Section 9.3. 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.Godsil and Royle (2001), Theorem 9.3.3. 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.Brouwer, Cohen, and Neumaier (1989).
References A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), Distance-Regular Graphs, Springer-Verlag, Berlin. Chris Godsil and Gordon Royle (2001), Algebraic Graph Theory, Graduate Texts in Math., Vol. 207, Springer-Verlag, New York. Brendan McKay (1981), Practical graph isomorphism, Congressus Numerantium, Vol. 30 (1981), pp. 45–87.
Related works Andries E. Brouwer and Willem H. Haemers (2012), Spectra of Graphs, Springer, New York. Paul Terwilliger and Jason Williford (2026), "An equitable partition for the distance-regular graph of the bilinear forms", Graphs and Combinatorics, vol. 42, article 42, 30 pp.
Notes