The Johnson graph 
has vertices given by the k-subsets
of 
, with two vertices
connected iff their intersection has size 
.
Johnson graphs are Hamilton-connected (Alspach 2013). They are also geometric (Koolen et al. 2023).
Special classes are summarized in the table below.
-
-An unrelated family of graphs corresponding to the skeletons of the Johnson solids may be termed Johnson skeleton graphs.
Cornet et al. (2026) determined the total domination number for 
and 
. For 
,
![gamma_t(J(n,2))=[(2(n-1))/3].](/images/equations/JohnsonGraph/NumberedEquation1.svg) |
(1)
|
For 
and 7, 
is four and five, respectively. For 
,
![gamma_t(J(n,3))={[(n^2-2n)/10] if n=0,1,2,3,9 (mod10) and n>=12; [(n^2-2n)/10]+1 otherwise.](/images/equations/JohnsonGraph/NumberedEquation2.svg) |
(2)
|
Here ![[x]](/images/equations/JohnsonGraph/Inline19.svg)
is the ceiling function. Cornet et al. (2026)
prove the formula analytically for 
and report integer linear programming verification
for 
and 9. They also prove that both the domination
number and total domination number
are nondecreasing in 
for 
. For 
and 
, the domination
number increases by at least one when 
increases by two, and by at least two if 
.
."
."
15 Nov 2023.