Equitable partition
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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_iv_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.
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_iv_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.
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
Text derived from https://en.wikipedia.org/w/index.php?oldid=1375953871 under CC BY-SA 4.0; modifications have been made.