ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.