TOPICS
Search

Johnson Skeleton Graph


JohnsonSkeletonGraphs

The skeleton graphs of the Johnson solids are polyhedral graphs which may be termed "Johnson skeleton graphs."

Special cases are summarized in the following table.

The Johnson skeleton graphs J_3 and J_(63) are minimal unit-distance forbidden graphs.

The skeleton of the gyroelongated pentagonal pyramid J_(11) appeared in Zaks (1976) and was used by Owens (1980) in the construction of a 76-node polyhedral quintic nonhamiltonian graph (though neither author identified the graph as the skeleton of a particular polyhedron).

An unrelated family of of graphs known as Johnson graphs J(n,k) are defined as graphs whose vertices given by the k-subsets of {1,...,n}, with two vertices connected iff their intersection has size k-1.


See also

Johnson Graph, Johnson Solid

Explore with Wolfram|Alpha

References

Owens, P. J. "On Regular Graphs and Hamiltonian Circuits, Including Answers to Some Questions of Joseph Zaks." J. Combin. Theory, Ser. B 28, 262-277, 1980.Zaks, J. "Pairs of Hamiltonian Circuits in 5-Connected Planar Graphs." J. Combin. Th. Ser. B, 116-131, 1976.

Cite this as:

Weisstein, Eric W. "Johnson Skeleton Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/JohnsonSkeletonGraph.html

Subject classifications