no. 10 · Friday 6 November 2026
Domination in Johnson graphs J(n, 3) for odd n
Abstract
In 2025 Cornet, Dravec, and Torres determined the domination number $γ(J(n,3))$ of the Johnson graph for every even $n \ge 6$, expressing it as a closed form $φ_n$ in terms of Fort-Hedlund covering numbers, and conjectured the same value for odd $n$. We prove this conjecture: $γ(J(n,3)) = φ_n$ for every odd $n \ge 7$. A dominating set of $J(n,3)$ is the same as a lotto design $\mathrm{LD}(n,3,3,2)$, and the lotto numbers $L(n,3,3,2)$, and hence $γ(J(n,3))$, were already determined for every $n$ by Bate (1978) and by Brouwer (1981); a short degree argument of Füredi, Székely, and Zubor (1996) gives the same lower bound for all $n \not\equiv 9, 10 \pmod{12}$. The contribution of this paper is therefore a new proof of the odd case, carried out within the bijective framework of Cornet, Dravec, and Torres.
- comments
- 18 pages. v3: adds the lower-bound argument of Füredi, Székely, and Zubor (1996); attributes the extremal structure for odd n >= 13 to Brouwer (1981, Theorem 2); shortens the proof of Lemma 2.4. v2: acknowledges that the result follows from earlier work of Bate (1978) and Brouwer (1981) on lotto designs; corrects several statements about prior work
- fields
- Combinatorics