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

From papers

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

diammin(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.

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

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

Solutions 0

No solutions have been posted yet.