Turán-Type Extremal Results for Distance-$k$ Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909005005193216 |
|---|---|
| author | He, Zhen Salia, Nika Tompkins, Casey Zhu, Xiutao |
| author_facet | He, Zhen Salia, Nika Tompkins, Casey Zhu, Xiutao |
| contents | We study Turán-type extremal problems for distance graphs, motivated by work of Csikvári, Bollobás, Tyomkyn, and Uzzell. We determine the maximum number of vertex pairs at distance three in an $n$-vertex graph with no triangle formed by these pairs, resolving the first case of a conjecture of Tyomkyn and Uzzell. We also determine the maximum number of vertex pairs at distance two in an $n$-vertex graph with no triangle formed by these pairs and give a complete characterization of the extremal graphs, settling another problem of Tyomkyn and Uzzell. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_28060 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Turán-Type Extremal Results for Distance-$k$ Graphs He, Zhen Salia, Nika Tompkins, Casey Zhu, Xiutao Combinatorics We study Turán-type extremal problems for distance graphs, motivated by work of Csikvári, Bollobás, Tyomkyn, and Uzzell. We determine the maximum number of vertex pairs at distance three in an $n$-vertex graph with no triangle formed by these pairs, resolving the first case of a conjecture of Tyomkyn and Uzzell. We also determine the maximum number of vertex pairs at distance two in an $n$-vertex graph with no triangle formed by these pairs and give a complete characterization of the extremal graphs, settling another problem of Tyomkyn and Uzzell. |
| title | Turán-Type Extremal Results for Distance-$k$ Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2604.28060 |