October 8, 2025Open Access

Oriented diameter of graphs with given domination number

Puntos clave

The oriented diameter of connected bridgeless graphs is confirmed to be at most ⌈(7γ+1)/2⌉, a sharp bound.
The oriented strong diameter is demonstrated to be at most 7γ-1, established via recursive structure techniques.
Induction on the domination number γ is used to validate the conjectured bounds on oriented diameters.
Contraction of unavoidable alternative subgraphs is a key method, indicating potential for future applications.

Resumen

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 7γ+12 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.

Leer artículo completoexternamente

Preguntar a la IA

Me gusta

Guardar

Ver artículo completo

Cite This Study

Wang et al. (Thu,) studied this question.

synapsesocial.com/papers/68e6494525bc5bdb9871394d https://doi.org/https://doi.org/10.48550/arxiv.2506.15997

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

Preguntar a la IA

Me gusta

Guardar

Ver artículo completo