Johnson图的割集和哈密尔顿圈

For a vertex $v$ in a graph $G$, a local cut at $v$ is a set of size $d(v)$ consisting of the vertex $x$ or the edge $vx$ for each $xin N(v)$. A diameter-increasing set in a graph $G$ is a set $U$ of vertices and edges such that the diameter of $G-U$ exceeds the diameter of $G$. In the present work, we first prove that every smallest generalized cut of Johnson graph $J(n,k)$ except $J(4,2)$ is a local cut. Then we show that every smallest diameter-increasing set in $J(n,k)$ except $J(n,2)$ and $J(6,3)$ is a subset of a local cut. Finally, we obtain that $J(n,k)$ has a Hamiltonian cycle for $n\\\\\\\\\\\\\\\\geq 3$.