Triangle-free graphs with diameter 2
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909214613438464 |
|---|---|
| author | Devillers, Alice Kamčev, Nina McKay, Brendan Catháin, Padraig Ó Royle, Gordon Van de Voorde, Geertrui Wanless, Ian Wood, David R. |
| author_facet | Devillers, Alice Kamčev, Nina McKay, Brendan Catháin, Padraig Ó Royle, Gordon Van de Voorde, Geertrui Wanless, Ian Wood, David R. |
| contents | There are finitely many graphs with diameter $2$ and girth 5. What if the girth 5 assumption is relaxed? Apart from stars, are there finitely many triangle-free graphs with diameter $2$ and no $K_{2,3}$ subgraph? This question is related to the existence of triangle-free strongly regular graphs, but allowing for a range of co-degrees gives the question a more extremal flavour. More generally, for fixed $s$ and $t$, are there infinitely many twin-free triangle-free $K_{s,t}$-free graphs with diameter 2? This paper presents partial results regarding these questions, including computational results, potential Cayley-graph and probabilistic constructions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_00246 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Triangle-free graphs with diameter 2 Devillers, Alice Kamčev, Nina McKay, Brendan Catháin, Padraig Ó Royle, Gordon Van de Voorde, Geertrui Wanless, Ian Wood, David R. Combinatorics There are finitely many graphs with diameter $2$ and girth 5. What if the girth 5 assumption is relaxed? Apart from stars, are there finitely many triangle-free graphs with diameter $2$ and no $K_{2,3}$ subgraph? This question is related to the existence of triangle-free strongly regular graphs, but allowing for a range of co-degrees gives the question a more extremal flavour. More generally, for fixed $s$ and $t$, are there infinitely many twin-free triangle-free $K_{s,t}$-free graphs with diameter 2? This paper presents partial results regarding these questions, including computational results, potential Cayley-graph and probabilistic constructions. |
| title | Triangle-free graphs with diameter 2 |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2406.00246 |