Connectivity versus Lin-Lu-Yau curvature
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912337436344320 |
|---|---|
| author | Chen, Kaizhe Liu, Shiping You, Zhe |
| author_facet | Chen, Kaizhe Liu, Shiping You, Zhe |
| contents | We explore the interaction between connectivity and Lin-Lu-Yau curvature of graphs systematically. The intuition is that connected graphs with large Lin-Lu-Yau curvature also have large connectivity, and vice versa. We prove that the connectivity of a connected graph is lower bounded by the product of its minimum degree and its Lin-Lu-Yau curvature. On the other hand, if the connectivity of a graph $G$ on $n$ vertices is at least $\frac{n-1}{2}$, then $G$ has positive Lin-Lu-Yau curvature. Moreover, the bound $\frac{n-1}{2}$ here is optimal. Furthermore, we prove that the edge-connectivity is equal to the minimum vertex degree for any connected graph with positive Lin-Lu-Yau curvature. As applications, we estimate or determine the connectivity and edge-connectivity of an amply regular graph with parameters $(d,α,β)$ such that $1\neq β\geq α$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_14352 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Connectivity versus Lin-Lu-Yau curvature Chen, Kaizhe Liu, Shiping You, Zhe Combinatorics We explore the interaction between connectivity and Lin-Lu-Yau curvature of graphs systematically. The intuition is that connected graphs with large Lin-Lu-Yau curvature also have large connectivity, and vice versa. We prove that the connectivity of a connected graph is lower bounded by the product of its minimum degree and its Lin-Lu-Yau curvature. On the other hand, if the connectivity of a graph $G$ on $n$ vertices is at least $\frac{n-1}{2}$, then $G$ has positive Lin-Lu-Yau curvature. Moreover, the bound $\frac{n-1}{2}$ here is optimal. Furthermore, we prove that the edge-connectivity is equal to the minimum vertex degree for any connected graph with positive Lin-Lu-Yau curvature. As applications, we estimate or determine the connectivity and edge-connectivity of an amply regular graph with parameters $(d,α,β)$ such that $1\neq β\geq α$. |
| title | Connectivity versus Lin-Lu-Yau curvature |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2504.14352 |