The Johnson graph vertices given by the k -subsetsvertices
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
(1)
For
(2)
Here ceiling function . Cornet et al. (2026)
prove the formula analytically for domination
number and total domination number
are nondecreasing in domination
number increases by at least one when
An independent vertex set in constant-weight
code of length Hamming
distance at least 4. For independence number by floor function .
Marín (2026) formalized this bound in Lean, with kernel acceptance recorded
by Palomar Registry (2026b).
The subsets of any set form a clique
in chromatic
number is at least Problem
835 in the Erdős problems collection asks
whether equality holds for any coloring of the subsets with subset contains a subset
of each color. Ma and Tang (2026) proved that the chromatic
number exceeds composite number . Stokes (2026) formalized
the result in Lean, with kernel acceptance recorded by Palomar Registry (2026a).
The existential question remains open.
See also Complete Graph ,
Johnson Skeleton Graph ,
Tetrahedral Johnson Graph ,
Triangular Graph
Explore with Wolfram|Alpha
References Alspach, B. "Johnson Graphs are Hamilton-Connected." Ars Math. Contemporanea 6 , 21-23, 2013. Brouwer, A. E.
"The Johnson Graphs." https://aeb.win.tue.nl/graphs/Johnson.html . Cornet,
M. G.; Dravec, T.; and Torres, P. "Domination and Total Domination in Johnson
Graphs." 3 Oct 2026. https://arxiv.org/abs/2610.04675 . DistanceRegular.org.
'Johnson Graphs https://www.math.mun.ca/distanceregular/indexes/johnsongraphs.html . Haemers,
W. H. "Distance-Regularity and the Spectrum of Graphs." Linear
Alg. Appl. 236 , 265-278, 1996. Haemers, W. H. and Spence,
E. "Graphs Cospectral with Distance-Regular Graphs." Linear Multilin.
Alg. 39 , 91-107, 1995. House of Graphs. Johnson Graphs. L(K_5) , L(K_6) ,
and others. Johnson, S. M. "A New Upper Bound for Error-Correcting
Codes." IRE Trans. Inf. Theory 8 , 203-207, 1962. https://doi.org/10.1109/TIT.1962.1057714 . Koolen,
J. H.; Yu, K.; Liang, X.; Choi, H.; and Markowsky, G. "Non-Geometric Distance-Regular
Graphs of Diameter at Least 3 with Smallest Eigenvalue at Least https://arxiv.org/abs/2311.09001 . Ma,
J. and Tang, Q. "A Note on Erdős Problem #835." Jan. 1, 2026.
https://github.com/QuanyuTang/erdos-problem-835/blob/7f131832bab5abfc903014ddb61efff21d56ae01/On_Problem_835.pdf . Marín,
C. "The Johnson Bound for the Independence Number of the Johnson Graph."
2026. https://github.com/karlesmarin/johnson-bound-palomar/tree/6eb8dad56bc31d0e5b0b64ad0931281bcbd71703 . Mütze,
T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems."
Not. Amer. Math. Soc. 71 , 583-592, 2024. https://doi.org/10.1090/noti2907 . Palomar
Registry. "Erdős Problem 835 when https://palomar-registry.org/entry.html?id=PALOMAR-2026-11-01-000008 . Palomar
Registry. "The Johnson Bound for the Independence Number of the Johnson Graph."
Entry PALOMAR-2026-11-06-000013, Nov. 6, 2026b. https://palomar-registry.org/entry.html?id=PALOMAR-2026-11-06-000013 . Stokes,
M. "Erdős Problem 835 when https://github.com/stokes/erdos835-palomar/tree/3a8d4cb348203b172c050917eaf1fa03679f002f . van
Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some
Distance-Regular Graphs." J. Algebraic Combin. 15 , 189-202, 2003. Referenced
on Wolfram|Alpha Johnson Graph
Cite this as:
Weisstein, Eric W. "Johnson Graph." From
MathWorld https://mathworld.wolfram.com/JohnsonGraph.html
Subject classifications More... Less...
has vertices given by the k-subsets
of 
, with two vertices
connected iff their intersection has size 
.
-
-
and 
. For 
,
![gamma_t(J(n,2))=[(2(n-1))/3].](/images/equations/JohnsonGraph/NumberedEquation1.svg)
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)
![[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 
.
corresponds to a binary constant-weight
code of length 
, weight 
, and pairwise Hamming
distance at least 4. For 
, Johnson (1962) bounded
the independence number by 
, where 
and 
for 
. Here 
is the floor function.
Marín (2026) formalized this bound in Lean, with kernel acceptance recorded
by Palomar Registry (2026b).
-element
subsets of any 
-element set form a clique
in 
, so its chromatic
number is at least 
. Problem
835 in the Erdős problems collection asks
whether equality holds for any 
. Equivalently, it asks for
a coloring of the 
-element subsets with 
colors such that every 
-element subset contains a 
-element subset
of each color. Ma and Tang (2026) proved that the chromatic
number exceeds 
when 
and 
is a composite number. Stokes (2026) formalized
the result in Lean, with kernel acceptance recorded by Palomar Registry (2026a).
The existential question remains open.
."
." 15 Nov 2023. 
Is Composite." Entry PALOMAR-2026-11-01-000008, Nov. 1,
2026a. 
Is Composite." 2026.