Improved bound on the number of edges of diameter-$k$-critical graphs
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_ | 1866909327020785664 |
|---|---|
| author | Wang, Xiaolin Zhang, Yanbo Zhu, Xiutao |
| author_facet | Wang, Xiaolin Zhang, Yanbo Zhu, Xiutao |
| contents | A graph is diameter-$k$-critical if its diameter equals $k$ and the deletion of any edge increases its diameter. The Murty-Simon Conjecture states that for any diameter-2-critical graph $G$ of order $n$, $e(G) \leq \lfloor \frac{n^2}{4}\rfloor$, with equality if and only if $G \cong K_{\lfloor \frac{n}{2}\rfloor,\lceil \frac{n}{2}\rceil}$. Füredi (JGT,1992) proved that this conjecture is true for sufficiently large $n$. Over two decades later, Loh and Ma (JCT-B, 2016) proved that $e(G) \leq \frac{n^2}{6}+o(n^2)$ for diameter-3-critical graphs $G$, and
$e(G) \leq \frac{3n^2}{k}$ for diameter-$k$-critical graphs $G$ with $k \geq 4$. In this paper, we improve the bound for diameter-$k$-critical graphs to $ \frac{n^2}{2k}+o(n^2)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_17491 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved bound on the number of edges of diameter-$k$-critical graphs Wang, Xiaolin Zhang, Yanbo Zhu, Xiutao Combinatorics A graph is diameter-$k$-critical if its diameter equals $k$ and the deletion of any edge increases its diameter. The Murty-Simon Conjecture states that for any diameter-2-critical graph $G$ of order $n$, $e(G) \leq \lfloor \frac{n^2}{4}\rfloor$, with equality if and only if $G \cong K_{\lfloor \frac{n}{2}\rfloor,\lceil \frac{n}{2}\rceil}$. Füredi (JGT,1992) proved that this conjecture is true for sufficiently large $n$. Over two decades later, Loh and Ma (JCT-B, 2016) proved that $e(G) \leq \frac{n^2}{6}+o(n^2)$ for diameter-3-critical graphs $G$, and $e(G) \leq \frac{3n^2}{k}$ for diameter-$k$-critical graphs $G$ with $k \geq 4$. In this paper, we improve the bound for diameter-$k$-critical graphs to $ \frac{n^2}{2k}+o(n^2)$. |
| title | Improved bound on the number of edges of diameter-$k$-critical graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2409.17491 |