Kurz–Lätsch conjecture on oriented diameter and domination number

From papers

Let GG be a bridgeless graph, and let γ(G)=γ\gamma(G)=\gamma be its domination number, where a dominating set is a vertex set DD such that every vertex in V(G)DV(G)\setminus D is adjacent to at least one vertex of DD. Write diam(G)\overrightarrow{\operatorname{diam}}(G) for the oriented diameter of GG.

Kurz–Lätsch conjecture. For every bridgeless graph GG with γ(G)=γ\gamma(G)=\gamma,

diam(G)7γ+12.\overrightarrow{\operatorname{diam}}(G)\leq \left\lceil\frac{7\gamma+1}{2}\right\rceil.

Kurz and Lätsch had previously proved the upper bound diam(G)4γ\overrightarrow{\operatorname{diam}}(G)\leq 4\gamma. Their conjecture seeks a sharper universal bound in terms of the domination number; the supplied source gives no resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Xiaolin Wang and Yaojun Chen, “Oriented diameter of graphs with given domination number”, arXiv:2506.15997 (2025).

Solutions 0

No solutions have been posted yet.