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

An unrelated family of graphs corresponding to the skeletons of the Johnson solids may be termed Johnson skeleton graphs.

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." 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.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.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