Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2508.19646 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914330271809536 |
|---|---|
| author | Eberhard, Sean Taranchuk, Vladislav Timmons, Craig |
| author_facet | Eberhard, Sean Taranchuk, Vladislav Timmons, Craig |
| contents | For each $t \ge 1$ let $W_t$ denote the class of graphs other than stars that have diameter $2$ and contain neither a triangle nor a $K_{2,t}$. The famous Hoffman--Singleton Theorem implies that $W_2$ is finite. Recently Wood suggested the study of $W_t$ for $t > 2$ and conjectured that $W_t$ is finite for all $t \ge 2$. In this note we show that (1) $W_3$ is infinite, (2) $W_5$ contains infinitely many regular graphs, and (3) $W_7$ contains infinitely many Cayley graphs. Our $W_3$ and $W_5$ examples are based on so-called crooked graphs, first constructed by de Caen, Mathon, and Moorhouse. Our $W_7$ examples are Cayley graphs with vertex set $\mathbb{F}_p^2$ for prime $p \equiv 11 \pmod {12}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19646 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Examples of diameter-2 graphs with no triangle or $K_{2,t}$ Eberhard, Sean Taranchuk, Vladislav Timmons, Craig Combinatorics 05C35 For each $t \ge 1$ let $W_t$ denote the class of graphs other than stars that have diameter $2$ and contain neither a triangle nor a $K_{2,t}$. The famous Hoffman--Singleton Theorem implies that $W_2$ is finite. Recently Wood suggested the study of $W_t$ for $t > 2$ and conjectured that $W_t$ is finite for all $t \ge 2$. In this note we show that (1) $W_3$ is infinite, (2) $W_5$ contains infinitely many regular graphs, and (3) $W_7$ contains infinitely many Cayley graphs. Our $W_3$ and $W_5$ examples are based on so-called crooked graphs, first constructed by de Caen, Mathon, and Moorhouse. Our $W_7$ examples are Cayley graphs with vertex set $\mathbb{F}_p^2$ for prime $p \equiv 11 \pmod {12}$. |
| title | Examples of diameter-2 graphs with no triangle or $K_{2,t}$ |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2508.19646 |