Lesson plan
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_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.
Article summary
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.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.