Return to Question

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.

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.

The Johnson graph $J(n,k)$ has as its vertices 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, any set of three vertices can be deleted from $J(5,3)$ and still gives rise to a Hamilton-connected 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 vertices 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.

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.

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$.

Thank you.

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.

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.

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.

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.

Thank you.

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.

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$.

Thank you.