Equitable partition

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 $V=V_{1}\cup V_{2}\cup \cdots \cup V_{r}$ where every vertex is contained in exactly one "cell" $V_{i}$, the edges within each cell form a regular graph, and for any two distinct cells $V_{i}$ and $V_{j}$ and every vertex $v_{i}\in V_{i}$, the number of edges $v_{i}v_{j}$ such that $v_{j}\in V_{j}$ is a constant $b_{ij}$, independent of the choice of $v_{i}\in V_{i}$.

The characteristic matrix $P$ of the partition has a row for each vertex and a column for each cell, with 1 in row $v$ and column $V_{i}$ if $v\in V_{i}$, 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. This fact can assist in studying eigenvalues of graphs with vertex-transitive automorphism group. It can also assist in determining isomorphism of graphs.

Matrix use

Equitable partitions allow collapsing $|V|\times |V|$ graphical matrices into smaller, $r\times r$ matrices while preserving the set of eigenvalues. Thus, they can facilitate spectral graph theory. For example, if $\pi$ is an equitable partition of $G$, then the characteristic polynomial of $A(G)$ is divisible by that of $A(G/\pi )$, where $G/\pi$ is a weighted directed graph formed by collapsing each cell to a single vertex. Thus, the eigenvalues of $A(G/\pi )$ are also eigenvalues of $A(G)$, but $A(G/\pi )$ 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.

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.