Johnson Graph - Properties

Properties

In the Johnson graph, the distance between every two vertices is half of the Hamming distance between the sets corresponding to the vertices. Johnson graphs are distance-transitive graphs: there is a graph automorphism mapping any pair of vertices to any other pair at the same distance.

As a consequence of being distance-transitive, every Johnson graph is also distance-regular. This means that, for every possible distance between two vertices in the graph, there is a triple of numbers such that, for every pair of vertices at distance from each other, has exactly neighbors at distance from, exactly neighbors at distance from, and exactly neighbors at distance from . These triples of numbers can be grouped into a matrix with one column per distance, called the intersection array of the graph, and this intersection array may be used to classify the distance-transitive graphs. It turns out that the intersection arrays of Johnson graphs are almost always enough to classify them completely: except for, each Johnson graph has an intersection array that is not shared with any other graph. However, the intersection array of is shared with three other distance-regular graphs that are not Johnson graphs.

Every Johnson graph is Hamilton-connected, meaning that every pair of vertices forms the endpoints of a Hamiltonian path in the graph. In particular this means that it has a Hamiltonian cycle.