On the oriented diameter of graphs with given minimum degree
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_ | 1866910910116790272 |
|---|---|
| author | Cochran, Garner Wang, Zhiyu |
| author_facet | Cochran, Garner Wang, Zhiyu |
| contents | Erdős, Pach, Pollack, and Tuza [\textit{J. Combin. Theory Ser. B, 47(1) (1989), 73-79}] proved that the diameter of a connected $n$-vertex graph with minimum degree $δ$ is at most $\frac{3n}{δ+1}+O(1)$. The oriented diameter of an undirected graph $G$, denoted by $\overrightarrow{\text{diam}}(G)$, is the minimum diameter of a strongly connected orientation of $G$. Bau and Dankelmann [\textit{European J. Combin., 49 (2015), 126-133}] showed that for every bridgeless $n$-vertex graph $G$ with minimum degree $δ$, $\overrightarrow{\text{diam}}(G) \leq \frac{11n}{δ+1}+9$. They also showed an infinite family of graphs with oriented diameter at least $\frac{3n}{δ+1} + O(1)$ and posed the problem of determining the smallest possible value $c$ for which $\overrightarrow{\text{diam}}(G) \leq c \cdot\frac{3n}{δ+1}+O(1)$ holds. In this paper, we show that the smallest value $c$ such that the upper bound above holds for all $δ\geq 2$ is $1$, which is best possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06587 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the oriented diameter of graphs with given minimum degree Cochran, Garner Wang, Zhiyu Combinatorics 05C12, 05C20, 05C35 Erdős, Pach, Pollack, and Tuza [\textit{J. Combin. Theory Ser. B, 47(1) (1989), 73-79}] proved that the diameter of a connected $n$-vertex graph with minimum degree $δ$ is at most $\frac{3n}{δ+1}+O(1)$. The oriented diameter of an undirected graph $G$, denoted by $\overrightarrow{\text{diam}}(G)$, is the minimum diameter of a strongly connected orientation of $G$. Bau and Dankelmann [\textit{European J. Combin., 49 (2015), 126-133}] showed that for every bridgeless $n$-vertex graph $G$ with minimum degree $δ$, $\overrightarrow{\text{diam}}(G) \leq \frac{11n}{δ+1}+9$. They also showed an infinite family of graphs with oriented diameter at least $\frac{3n}{δ+1} + O(1)$ and posed the problem of determining the smallest possible value $c$ for which $\overrightarrow{\text{diam}}(G) \leq c \cdot\frac{3n}{δ+1}+O(1)$ holds. In this paper, we show that the smallest value $c$ such that the upper bound above holds for all $δ\geq 2$ is $1$, which is best possible. |
| title | On the oriented diameter of graphs with given minimum degree |
| topic | Combinatorics 05C12, 05C20, 05C35 |
| url | https://arxiv.org/abs/2409.06587 |