TOPICS
Search

Johnson Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
JohnsonGraphs

The Johnson graph J(n,k) has vertices given by the k-subsets of {1,...,n}, with two vertices connected iff their intersection has size k-1.

Johnson graphs are Hamilton-connected (Alspach (2013). They are also geometric (Koolen et al. 2023).

Special classes are summarized in the table below.

J(n,k)graph
J(4,2)octahedral graph
J(n,1)complete graph K_n
J(n,2)n-triangular graph
J(n,3)n-tetrahedral Johnson graph

See also

Complete 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." http://www.win.tue.nl/~aeb/graphs/Johnson.html.DistanceRegular.org. 'Johnson Graphs J(n,m)." http://www.distanceregular.org/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.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 -3." 15 Nov 2023. https://arxiv.org/abs/2311.09001.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--A Wolfram Web Resource. https://mathworld.wolfram.com/JohnsonGraph.html

Subject classifications