On Diameter Stability of the Johnson Graph

Abstract

In this paper, we study the edge deletion preserving the diameter of the Johnson graph $J(n,k)$. Let $u{n}^{-}(G)$ be the maximum number of edges of a graph $G$ whose removal maintains its diameter. For Johnson graph $J(n,k)$, we give upper and lower bounds to the number $u{n}^{-}(J(n,k))$, namely:$(\genfrac{}{}{0ex}{}{k}{2})(\genfrac{}{}{0ex}{}{n}{k+1})\le u{n}^{-}(J(n,k))\le (\genfrac{}{}{0ex}{}{k+1}{2})(\genfrac{}{}{0ex}{}{n}{k+1})+\lceil (1+\frac{1}{2k})((\genfrac{}{}{0ex}{}{n}{k})–1\rceil ,$ for $n\ge 2k\ge 2$.