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

About 1 year old · traced to

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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.