MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The Johnson graph $J(n,k)$ has vertices which are the $k$-subsets of $\{1, 2, \dots, n\}$ where two vertices are adjacent iff their intersection has size $k-1$. A graph is hamilton-connected if every two vertices are joined by a hamiltonian path. A recent paper by Alspach shows that Johnson graphs are hamilton-connected.

I'm interested in how many vertices can be removed from $J(n,k)$ while still requiring that the induced subgraph be hamilton-connected. For example, the picture below shows $J(5,3)$ and an induced subgraph resulting from deleting four vertices. The induced subgraph is no longer hamilton-connected; at the very least there is no hamiltonian path from $345$ to $245$. However, all collections of three vertices can be deleted from $J(5,3)$ and still give rise to a hamilton-connected induced subgraph.

J(5,3) and an induced subgraph

I searched the literature for anything that might be helpful for this question. I found a paper by Naimi and Shaw on induced subgraphs of Johnson graphs, but it doesn't deal with hamiltonicity. A sufficient condition proved by Chvátal and Erdős is that if a graph $G$'s independence number $\alpha(G)$ is strictly less than its vertex connectivity $\kappa(G)$ then it is hamilton-connected. While $\kappa(J(n,k))=k(n-k)$, $\alpha(J(n,k))$ does not seem to be as readily understood, and so I'm not sure if the desired inequality would hold for the original graph or any of its induced subgraphs. If the induced subgraph $H$ has at least four vertices, a necessary condition seems to be that that $H$ has no verices of degree two. For if $x$ had exactly two neighbors $v_1$ and $v_2$, any hamiltonian path through $H$ not starting or ending at $x$ would have to use the two edges incident to $x$, thus the path $v_1xv_2$ couldn't be extended to a hamiltonian path from $v_1$ to $v_2$.

For the reason given above, we can always find a collection of $k(n-k)-2$ vertices to delete that leaves a given vertex with degree two, and thus the resulting induced subgraph would not be hamilton-connected.

So I guess my question can be rewritten as, if $S \subset V(J(n,k))$ such that $|S| < k(n-k)-2$, is $J(n,k)-S$ always hamilton-connected?

Thank you.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.