On cores of distance-regular graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913774381826048 |
|---|---|
| author | Geertsema, Annemarie Godsil, Chris Guo, Krystal |
| author_facet | Geertsema, Annemarie Godsil, Chris Guo, Krystal |
| contents | We look at the question of which distance-regular graphs are core-complete, meaning they are isomorphic to their own core or have a complete core. We build on Roberson's homomorphism matrix approach by which method he proved the Cameron-Kazanidis conjecture that strongly regular graphs are core-complete. We develop the theory of the homomorphism matrix for distance-regular graphs of diameter $d$.
We derive necessary conditions on the cosines of a distance-regular graph for it to admit an endomorphism into a subgraph of smaller diameter $e<d$. As a consequence of these conditions, we show that if $X$ is a primitive distance-regular graph where the subgraph induced by the set of vertices furthest away from a vertex $v$ is connected, any retraction of $X$ onto a diameter-$d$ subgraph must be an automorphism, which recovers Roberson's result for strongly regular graphs as a special case for diameter $2$.
We illustrate the application of our necessary conditions through computational results. We find that no antipodal, non-bipartite distance-regular graphs of diameter 3, with degree at most $50$ admits an endomorphism to a diameter 2 subgraph. We also give many examples of intersection arrays of primitive distance-regular graphs of diameter $3$ which are core-complete. Our methods include standard tools from the theory of association schemes, particularly the spectral idempotents.
Keywords: algebraic graph theory, distance-regular graphs, association schemes, graph homomorphisms |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_00129 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On cores of distance-regular graphs Geertsema, Annemarie Godsil, Chris Guo, Krystal Combinatorics Primary 05E30, Secondary 05C15, 05C50 We look at the question of which distance-regular graphs are core-complete, meaning they are isomorphic to their own core or have a complete core. We build on Roberson's homomorphism matrix approach by which method he proved the Cameron-Kazanidis conjecture that strongly regular graphs are core-complete. We develop the theory of the homomorphism matrix for distance-regular graphs of diameter $d$. We derive necessary conditions on the cosines of a distance-regular graph for it to admit an endomorphism into a subgraph of smaller diameter $e<d$. As a consequence of these conditions, we show that if $X$ is a primitive distance-regular graph where the subgraph induced by the set of vertices furthest away from a vertex $v$ is connected, any retraction of $X$ onto a diameter-$d$ subgraph must be an automorphism, which recovers Roberson's result for strongly regular graphs as a special case for diameter $2$. We illustrate the application of our necessary conditions through computational results. We find that no antipodal, non-bipartite distance-regular graphs of diameter 3, with degree at most $50$ admits an endomorphism to a diameter 2 subgraph. We also give many examples of intersection arrays of primitive distance-regular graphs of diameter $3$ which are core-complete. Our methods include standard tools from the theory of association schemes, particularly the spectral idempotents. Keywords: algebraic graph theory, distance-regular graphs, association schemes, graph homomorphisms |
| title | On cores of distance-regular graphs |
| topic | Combinatorics Primary 05E30, Secondary 05C15, 05C50 |
| url | https://arxiv.org/abs/2504.00129 |