Smallest Generalized Cuts and Diameter-Increasing Sets of Johnson Graphs

Abstract

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 $x\in N(v)$. A set $U\subseteq V(G)\cup E(G)$ is a diameter-increasing set of $G$ if the diameter of $G–U$ is greater than the diameter of $G$. In the present work, we first prove that every smallest generalized cutset of Johnson graph $J(n,k)$ is a local cut except for $J(4,2)$. Then we show that every smallest diameter-increasing set in $J(n,k)$ is a subset of a local cut except for $J(n,2)$ and $J(6,3)$.