The minimum oriented diameter bound in terms of vertex-cover number

About 18 years old · traced to

Let GG be a bridgeless connected graph, and let γ(G)\gamma(G) denote its vertex-cover number. Define the minimum oriented diameter by

diam⟶min⁡(G)=min⁡{diam(G→):G→ is an orientation of G}.\overset{\longrightarrow}{diam}_{\min}(G)=\min\{diam(\overset{\rightarrow}{G}):\overset{\rightarrow}{G}\text{ is an orientation of }G\}.

Minimum oriented diameter conjecture.

Ξ(γ)=⌈7γ(G)+12⌉.\Xi(\gamma)=\left\lceil\frac{7\gamma(G)+1}{2}\right\rceil.

The paper proves the upper bound Ξ(γ)≤4γ\Xi(\gamma)\leq 4\gamma and presents the displayed formula as the expected true upper bound; its status is not resolved in the supplied text.

References

Primary source

Sascha Kurz and Martin Laetsch, “Bounds for the minimum oriented diameter”, arXiv:0804.1294 (2008).

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.