← All problems

Intermediate-value conjecture for orientable total domination numbers

3 years old · traced to

Let G∈CG\in\mathcal{C} be a graph, and let domt(G){\rm dom}_t(G) and DOMt(G){\rm DOM}_t(G) denote its lower and upper orientable total domination numbers. For an orientation ff of GG, write GfG_f for the resulting oriented graph and γt(Gf)\gamma_t(G_f) for its total domination number. Intermediate-value conjecture. For every integer cc satisfying

domt(G)≤c≤DOMt(G),{\rm dom}_t(G)\leq c\leq {\rm DOM}_t(G),

there exists an orientation ff of GG such that

γt(Gf)=c.\gamma_t(G_f)=c.

This extends the corresponding result known for complete graphs and complete bipartite graphs. The source attributes the conjecture to the authors of the cited earlier work, and no resolution is given here.

References
  1. Sarah E. Anderson, Tanja Dravec, Daniel Johnston and Kirsti Kuenzel, “Orientable total domination in graphs”, arXiv:2311.16307 (2023).

Progress summary

Refreshed
Open · progress reported

A reader-submitted proof claims to establish the conjecture for every graph, but no independent assessment has confirmed it.

The conjecture asks whether every integer between the lower and upper orientable total domination numbers is attained by some orientation. The 2023 source attributes it to earlier work and does not resolve it.

Known results

  • The analogous intermediate-value statement is known for complete graphs.
  • For complete bipartite graphs, every kk with 4≤k≤m+24\leq k\leq m+2 occurs for Km,nK_{m,n} when 2≤m≤n2\leq m\leq n (2023 source).

November 7, 2026 community submission

A submitted proof argues that safe arc reversals connect the relevant orientations while changing the total domination number by at most one, thereby attaining every intermediate value without a connectedness assumption. The argument is unverified.

Current status (as of November 2026): The conjecture remains open in the published record, while a community-submitted general proof is an unverified claim of progress.

Sources

Solutions 1

For every finite graph admitting a valid orientation, every integer between its lower and upper orientable total domination numbers is attained. This proves the interpolation conjecture, including disconnected graphs.See full solutionHide full solution

The proof proceeds by induction on the number of edges on which two valid orientations disagree. If every disagreeing arc is the unique incoming arc at its head, a forced-head argument transfers every total dominating set from the first orientation to the target. Otherwise, a suitable arc can be reversed while retaining positive indegree; adjoining one vertex repairs total domination. Whenever the target value is strictly higher, this safe flip decreases disagreement and raises the available upper bound by at most one, yielding every intermediate integer. No connectedness assumption is needed. The proof does not assume that all valid orientations are connected by single-edge flips.

Complete proof and verification sources: Interpolation of orientable total domination by safe arc reversals: a proof of the Hansen-Lai-Yue conjecture (JCMCC 1999; Anderson-Dravec-Johnston-Kuenzel Conjecture 3.1, arXiv:2311.16307) · PDF.

The paper page includes proof-sources.json and extract_sources.py, which reconstruct the proof sources. The Lean certificate proves the stated finite-graph theorem. The paper records formalization and trust limits.

This is an AI-assisted research preprint. Internal review is not external journal peer review; bounded prior-art searches do not certify worldwide priority.