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

The characteristic matrix ${\displaystyle P}$ of the partition has a row for each vertex and a column for each cell, with 1 in row ${\displaystyle v}$ and column ${\displaystyle V_{i}}$ if ${\displaystyle v\in V_{i}}$, otherwise 0.