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.