Equitable partitions of regular graphs, and perfect sets in normal Cayley graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917505522466816 |
|---|---|
| author | Bailey, R. A. Cameron, Peter J. Zhou, Sanming |
| author_facet | Bailey, R. A. Cameron, Peter J. Zhou, Sanming |
| contents | An equitable partition of a graph $\Ga$ is a partition $\{V_1, \ldots, V_m\}$ of its vertex set such that for each pair $i, j$ all vertices in $V_i$ have the same number of neighbours in $V_j$. When $m=2$, $V_1$ is called an $(a, b)$-perfect set in $\Ga$, where $a$ is the number of neighbours in $V_1$ of each vertex in $V_1$, and $b$ is the number of neighbours in $V_1$ of each vertex in $V_2$. In this paper we first derive general necessary conditions for a regular graph to admit two equitable partitions. As a corollary we obtain necessary conditions for the existence of an $(a,b)$-perfect set in a regular graph in terms of an arbitrary equitable partition. With the help of these results we then obtain necessary conditions for the existence of an $(a,b)$-perfect set in a normal Cayley graph in terms of the irreducible characters of the underlying group. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_17376 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Equitable partitions of regular graphs, and perfect sets in normal Cayley graphs Bailey, R. A. Cameron, Peter J. Zhou, Sanming Combinatorics 05C25, 05C69, 94B99 An equitable partition of a graph $\Ga$ is a partition $\{V_1, \ldots, V_m\}$ of its vertex set such that for each pair $i, j$ all vertices in $V_i$ have the same number of neighbours in $V_j$. When $m=2$, $V_1$ is called an $(a, b)$-perfect set in $\Ga$, where $a$ is the number of neighbours in $V_1$ of each vertex in $V_1$, and $b$ is the number of neighbours in $V_1$ of each vertex in $V_2$. In this paper we first derive general necessary conditions for a regular graph to admit two equitable partitions. As a corollary we obtain necessary conditions for the existence of an $(a,b)$-perfect set in a regular graph in terms of an arbitrary equitable partition. With the help of these results we then obtain necessary conditions for the existence of an $(a,b)$-perfect set in a normal Cayley graph in terms of the irreducible characters of the underlying group. |
| title | Equitable partitions of regular graphs, and perfect sets in normal Cayley graphs |
| topic | Combinatorics 05C25, 05C69, 94B99 |
| url | https://arxiv.org/abs/2605.17376 |