Johnson Graph

Author

Eric W. Weisstein
November 27, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/JohnsonGraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/JohnsonGraph.html.

©2023 Wolfram Research, Inc. except for portions noted otherwise

Definition

The Johnson graph J(n, e) has vertices the e-subsets of {1, ..., n}, and x connected to y if and only if their intersection has size e - 1. 

J(n,1) are the Complete Graphs.
J(n,2) are more commonly called Triangular Graphs.
J(n,3) are sometimes called the Tetrahedral Graphs.
J(7,3) is a famous, distance regular graph 

The complement of a Kneser graph is sometimes known as a Johnson graph.

e1=Edges[JohnsonGraph[10,5]];

e2=List@@@EdgeList[JohnsonGraphSW[10,5]];

e1===e2

Embeddings

l=Select[Sort[{"Johnson"/.GraphData[#,"NotationRules"],#,GraphData[#,"V"]}&/@Select[GraphData["Johnson"],GraphData[#,"Embeddings"]=!={}&]],Last[#]<11&]

GraphicsGrid[Partition[Show[GraphData[#[[2]]],PlotLabel->StringReplace[ToString[#[[1]]],{"{"->"(","}"->")"}]<>"-Johnson graph"]&/@l,3],ImageSize->400]

Enumeration

GraphData[{"Johnson",{7,3}},"#"]

RecognizeGraph[{"Johnson",{10,5}}]

FastIsomorphicQ[JohnsonGraph[7,3],JohnsonGraph[7,4]]

GraphPlot3D[#/.List->Rule&/@JohnsonGraph[7,3],Boxed->False]

Table[{n,RecognizeGraph[JohnsonGraph[n,1]]},{n,12}]

Table[{n,RecognizeGraph[JohnsonGraph[n,2]]},{n,12}]

Table[{n,RecognizeGraph[JohnsonGraph[n,3]]},{n,12}]

j=GraphData["Johnson"]

DeleteCases[j,{"Complete"|"Johnson"|"Tetrahedral"|"Triangular",_}]

"Johnson"/.GraphData["OctahedralGraph","NotationRules"]

GraphData

GraphDataClassString

GraphDataClassString["Johnson"]

GraphDataString

Table[Print[GraphDataString[JohnsonGraph[n,k],
"Name"->"("<>ToString[n]<>","<>ToString[k]<>")\[Hyphen]Johnson graph",
"StandardName"->{"Johnson",{n,k}},
"Information"->"JohnsonGraph",
TimeConstraint->60
]],{k,3,4},{n,k+1,10}]

With[{n=10,k=5},Print[GraphDataString[JohnsonGraph[n,k],
"Name"->"Johnson graph ("<>ToString[n]<>","<>ToString[k]<>")",
"StandardName"->{"Johnson",{n,k}},
"NotationRules"->{"Johnson"->{n,k}},
"Information"->"JohnsonGraph",
Debug->True,
TimeConstraint->60
]]]