Shirt a Phobia

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.^[1] This fact can assist in studying eigenvalues of graphs with vertex-transitive automorphism group. It can also assist in determining isomorphism of graphs.^[2]

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.^[3] 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.^[4] 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.^[5]

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.

Notes

^ Godsil and Royle (2001), Section 9.3.
^ McKay (1981).
^ Godsil and Royle (2001), Section 9.3.
^ Godsil and Royle (2001), Theorem 9.3.3.
^ Brouwer, Cohen, and Neumaier (1989).

[rdp-we-cite_note-1] Godsil and Royle (2001), Section 9.3.

[rdp-we-cite_note-2] McKay (1981).

[rdp-we-cite_note-3] Godsil and Royle (2001), Section 9.3.

[rdp-we-cite_note-4] Godsil and Royle (2001), Theorem 9.3.3.

[rdp-we-cite_note-5] Brouwer, Cohen, and Neumaier (1989).

[1]

[2]

[3]

[4]

[5]

Sample Page

Equitable partitions from automorphisms

Matrix use

References

Notes