Oriented diameter of graphs with diameter $4$ and given edge girth
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_ | 1866917047154245632 |
|---|---|
| author | Lin, Jifu You, Lihua |
| author_facet | Lin, Jifu You, Lihua |
| contents | Let $f(d)$ be the smallest value for which every bridgeless graph $G$ with diameter $d$ admits a strong orientation $\overrightarrow{G}$ such that the diameter of $\overrightarrow{G}$ is at most $f(d)$. Chvátal and Thomassen (JCT-B, 1978) obtained general bounds for $f(d)$ and proved that $f(2)=6$. Kwok et al. (JCT-B, 2010) proved that $9\leq f(3)\leq 11$. Wang and Chen (JCT-B, 2022) determined $f(3)=9$. Babu et al. (DAM, 2021) showed $f(4)\leq 21$.
In this paper, we introduce a new approach to studying $f(d)$ via the edge girth of a bridgeless graph $G$, denoted by $g^*(G)=\max\{l_G(e)\mid e\in E(G)\}$, where $l_G(e)$ is the length of the shortest cycle containing $e$ in $G$. Then we define $F(d,g^*)=\max\{\overrightarrow{diam}(G)\mid G\text{ is bridgeless},d(G)=d,g^*(G)=g^*\}$, and show $f(d)=\max\{F(d,g^*)\mid 2\leq g^*\leq 2d+1\}$. As the main result of this paper, we establish $F(4,2)=4$, $F(4,9)=12$, $F(4,3)\le 12$, and $F(4,g^*)\le 13$ for $g^*\in\{6,7,8\}$, and we propose two open problems for further research. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_23517 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Oriented diameter of graphs with diameter $4$ and given edge girth Lin, Jifu You, Lihua Combinatorics 05C12, 05C20 Let $f(d)$ be the smallest value for which every bridgeless graph $G$ with diameter $d$ admits a strong orientation $\overrightarrow{G}$ such that the diameter of $\overrightarrow{G}$ is at most $f(d)$. Chvátal and Thomassen (JCT-B, 1978) obtained general bounds for $f(d)$ and proved that $f(2)=6$. Kwok et al. (JCT-B, 2010) proved that $9\leq f(3)\leq 11$. Wang and Chen (JCT-B, 2022) determined $f(3)=9$. Babu et al. (DAM, 2021) showed $f(4)\leq 21$. In this paper, we introduce a new approach to studying $f(d)$ via the edge girth of a bridgeless graph $G$, denoted by $g^*(G)=\max\{l_G(e)\mid e\in E(G)\}$, where $l_G(e)$ is the length of the shortest cycle containing $e$ in $G$. Then we define $F(d,g^*)=\max\{\overrightarrow{diam}(G)\mid G\text{ is bridgeless},d(G)=d,g^*(G)=g^*\}$, and show $f(d)=\max\{F(d,g^*)\mid 2\leq g^*\leq 2d+1\}$. As the main result of this paper, we establish $F(4,2)=4$, $F(4,9)=12$, $F(4,3)\le 12$, and $F(4,g^*)\le 13$ for $g^*\in\{6,7,8\}$, and we propose two open problems for further research. |
| title | Oriented diameter of graphs with diameter $4$ and given edge girth |
| topic | Combinatorics 05C12, 05C20 |
| url | https://arxiv.org/abs/2507.23517 |