arXiv
Open Access
2025
Oriented diameter of graphs with given domination number
Xiaolin Wang
Yaojun Chen
Abstrak
Let $G$ be a connected bridgeless graph with domination number $γ$. The oriented diameter (strong diameter) of $G$ is the smallest integer $d$ for which $G$ admits a strong orientation with diameter (strong diameter) $d$. Kurz and Lätsch (2012) conjectured the oriented diameter of $G$ is at most $\lceil \frac{7γ+1}{2}\rceil$ and the bound is sharp. In this paper, we confirm the conjecture by induction on $γ$ through contracting an unavoidable alternative subgraph, which holds potential for future applications. Moreover, we show the oriented strong diameter of $G$ is at most $7γ-1$ by using the same recursive structure, and the bound is best possible.
Topik & Kata Kunci
Penulis (2)
X
Xiaolin Wang
Y
Yaojun Chen
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2025
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓