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)\).