EUVIMEDEUVIMED entdecken
Crossref

Oriented diameter of graphs with diameter 4 and given edge girth

Jifu Lin, Lihua You

Discrete Applied Mathematics · 2026-10 · 391 · 413-431

DOI: 10.1016/j.dam.2026.05.012 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Applied Mathematics, 2026-10. Verfasst von Jifu Lin und 1 weiteren Autor:innen. Die Arbeit nennt 18 Literaturangaben. Gefördert von: National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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\'atal 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.

Förderung

  • National Natural Science Foundation of China

Zitieren

APA

Lin, J., & You, L. (2026). Oriented diameter of graphs with diameter 4 and given edge girth. Discrete Applied Mathematics, 391, 413-431. https://doi.org/10.1016/j.dam.2026.05.012

Vancouver

Lin J, You L. Oriented diameter of graphs with diameter 4 and given edge girth. Discrete Applied Mathematics. 2026;391:413-431. doi:10.1016/j.dam.2026.05.012

BibTeX
@article{Lin2026,
  author = {Lin, Jifu and You, Lihua},
  title = {Oriented diameter of graphs with diameter 4 and given edge girth},
  journal = {Discrete Applied Mathematics},
  year = {2026},
  volume = {391},
  pages = {413--431},
  doi = {10.1016/j.dam.2026.05.012}
}
Kostenlos starten →