Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 6 (2013) 21–23
Johnson graphs are Hamilton-connected
Brian Alspach
School of Mathematical and Physical Sciences University of Newcastle
Callaghan, NSW 2308, Australia
Received 15 December 2011, accepted 15 January 2012, published online 1 June 2012
Abstract
We prove that the Johnson graphs are Hamilton-connected and apply this to obtain that
another family of graphs is Hamilton-connected.
Keywords: Hamilton path, Johnson graph, Hamilton-connected.
Math. Subj. Class.: 05C70
1 Main Result
The Johnson graph J(n, k), 0 ≤ k ≤ n, is defined by letting the vertices correspond to
the k-subsets of an n-set, where two vertices are adjacent if and only if the corresponding
k-subsets have exactly k − 1 elements in common. A graph is Hamilton-connected if for
any pair of distinct vertices u, v there is a Hamilton path whose terminal vertices are u and
v. The graph with a single vertex is trivially Hamilton-connected.
In a recent paper [1], I needed a certain graph to be Hamilton-connected. This graph,
defined below, contains vertex-disjoint Johnson graphs. The result I needed is embodied in
the corollary below.
Theorem 1.1. The Johnson graph J(n, k) is Hamilton-connected for all n ≥ 1.
Proof. For ease of exposition, instead of talking about the vertex corresponding to a subset,
we shall simply treat the subsets as if they are vertices so that we use equality notation
between vertices and sets. The graphs J(n, k) and J(n, n − k) are isomorphic via the
mapping that takes a k-subset to its complement.
The graphs J(n, 0) and J(n, n), n ≥ 1, are isomorphic to the single vertex K1 and
trivially Hamilton-connected. The graphs J(n, 1) and J(n, n− 1), n ≥ 1, are isomorphic
to the complete graph Kn. Complete graphs certainly are Hamilton-connected.
We proceed by double induction and when considering J(n, k), the induction hypothe-
ses are: J(m, k′) is Hamilton-connected whenever k′ < k and m ≥ k′, or J(m, k) is
E-mail address: brian.alspach@newcastle.edu.au (Brian Alspach)
Copyright c© 2013 DMFA Slovenije
22 Ars Math. Contemp. 6 (2013) 21–23
Hamilton-connected whenever m < n and m ≥ k. As noted above, J(n, 1) is Hamilton-
connected for all n ≥ 1. For a fixed k we start with J(k, k) and then proceed by going
from J(n− 1, k) to J(n, k). Thus, the induction hypotheses make sense.
If k ≤ n ≤ 2k − 1, then n − k < k so that J(n, n − k) is Hamilton-connected by
hypothesis. This, in turn, implies that J(n, k) is Hamilton-connected because J(n, k) and
J(n, n − k) are isomorphic. Thus, it follows that J(n, k) is Hamilton-connected for all n
satisfying k ≤ n ≤ 2k − 1.
For the remaining cases we need to actually show how to find appropriate Hamilton
paths. The symmetric group Sn acts in the obvious way on the vertex set of J(n, k).
This action is transitive so that it suffices to find a Hamilton path from the vertex u =
{1, 2, 3, . . . , k} to any other vertex. Let v = {a1, a2, . . . , ak} be an arbitrary vertex.
If there is an element x of {1, 2, . . . , n} belonging to neither of the sets, we may relabel
elements so that n is missing from both sets. Thus, both k-sets are subsets of {1, 2, . . . , n−
1}. By induction there is a Hamilton path from u to v in J(n− 1, k). Because the vertices
that are adjacent along that path also are adjacent in J(n, k), let P ′ be the corresponding
path from u to v in J(n, k). The path P ′ contains all the vertices corresponding to k-subsets
that do not contain n.
Let w1 = {y1, y2, . . . , yk−1, yk} and w2 = {y1, y2, . . . , yk−1, zk} be two adjacent
vertices on P ′. The vertex w1 is adjacent to the vertex w3 = {y2, . . . , yk−1, yk, n}, and the
vertex w2 is adjacent to the vertex w4 = {y2, . . . , yk−1, zk, n}.
The subgraph X induced by J(n, k) on all the subsets containing n clearly is isomor-
phic to J(n− 1, k− 1). Thus, there is a path from w3 to w4 spanning all the vertices of X .
Thus, remove the edge of P ′ between w1 and w2, add the edges w1w3 and w2w4, and then
add the path from w3 to w4 spanning X . The resulting path is a Hamilton path in J(n, k)
with u and v as terminal vertices.
If n > 2k, then there always is an element x missing both subsets and the preceding
argument establishes that J(n, k) is Hamilton-connected. If n = 2k, there is exactly one
subset that fails the criterion, namely, the complement of {1, 2, . . . , k}. So we need to find
a Hamilton path in J(2k, k) from u to its complement.
Consider the k-subsets of {1, 2, . . . , 2k} not containing the element 2k. The subgraph
induced by J(2k, k) on this collection of subsets is isomorphic to the graph J(2k − 1, k).
It is Hamilton-connected by induction so that there is a Hamilton path from u to w =
{1, 2, . . . , k − 1, 2k − 1}. Let P be the copy of this path in J(2k, k).
Now consider all the k-subsets of {1, 2, . . . , 2k} that contain the element 2k. The
subgraph Y ′ induced on this collection of sets is isomorphic to J(2k − 1, k − 1) so that
it has a spanning path from {1, 2, . . . , k − 1, 2k} to {k + 1, k + 2, . . . , 2k}. Because the
intermediate terminal vertices on the two paths are adjacent, we have a Hamilton path in
J(2k, k) from u to its complement. This completes the proof.
The corollary below is the real target of this short paper. We need to define a particular
graph first. Let A = {a1, a2, . . . , am} be a non-empty subset of {0, 1, 2, . . . , n} such that
the elements are listed in the order a1 < a2 < · · · < am. We define the graph QJ(n,A)
in the following way. For each ai ∈ A, we include a copy of the Johnson graph J(n, ai).
Thus far the Johnson graphs are vertex-disjoint. We then insert edges between J(n, ai) and
J(n, ai+1), for each i, using set inclusion, that is, we join an ai-subset S1 and an ai+1-
subset S2 if S1 is contained in S2. The graph QJ(n,A) can be pictured as having levels
made up of Johnson graphs with edges between successive levels based on set inclusion.
B. Alspach: Johnson graphs are Hamilton-connected 23
Corollary 1.2. The graph QJ(n,A) is Hamilton-connected for all n ≥ 1.
Proof. If A is a singleton set, then QJ(n,A) is a Johnson graph and the result follows
from Theorem 1.1. Hence, we assume that A has at least two elements. Suppose that u and
v are two vertices of QJ(n,A) lying at different levels, where u has cardinality ai, v has
cardinality aj , and ai < aj . Construct a path starting at u that spans the vertices at level ai
and terminates at an arbitrary vertex ui at level ai.
Choose a neighbor ui+1 of ui at level ai+1 making certain it is distinct from v if j =
i+ 1. Then add the edge from ui to ui+1 followed by a path spanning the vertices at level
ai+1. If v happens to lie at this level make certain the path terminates at v. Otherwise, the
path can terminate at any vertex at level ai+1.
It is obvious how to continue this until we have a path starting at u, terminating at v,
and spanning all the vertices at levels ai, ai+1 up through level aj . If this happens to be
all the levels of QJ(n,A), then we have found a Hamilton path joining u and v. If we are
missing levels, we then continue as follows.
If there are missing levels above level aj , then remove an edge xy of the current path at
level aj and take distinct neighbors x′ and y′ of x and y, respectively, at level aj+1. Then
extend to a larger path by taking a path joining x′ and y′ spanning all the vertices at level
aj+1. If x and y don’t have distinct neighbors at level aj+1, then aj+1 = n and the level is
the singleton vertex w = {1, 2, 3, . . . , n} which is adjacent to everything at level aj so that
we replace the edge xy of the path with the 2-path xwy.
It is obvious how to continue adding the vertices one level at a time until we finish with
the top level. We also can do the analogous extension with the levels below ai until we
achieve a Hamilton path in Q(n,A) that has u and v as terminal vertices.
If u and v are at the same level. Then we start with a path spanning level ai that has u
and v as terminal vertices. We then extend the path through the other levels as above. This
completes the proof.
Corollary 1.2 allows us to process a variety of collections of sets of different cardinal-
ities where we can move from one set to another either by a revolving door operation or
restricted inclusions. This is what was required in [1].
References
[1] B. Alspach, Hamilton paths in Cayley graphs on Coxeter groups: I, preprint.