In this paper, we study the edge deletion preserving the diameter of the Johnson graph \(J(n,k)\). Let \(un^-(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 \(un^-(J(n,k))\), namely:\(\binom{k}{2}\binom{n}{k+1} \leq un^-(J(n,k)) \leq \binom{k+1}{2} \binom{n}{k+1} + \lceil(1+\frac{1}{2k})(\binom{n}{k} – 1\rceil,\) for \(n \geq 2k \geq 2\).
Citation
Ling Wang, Heping Zhang. On Diameter Stability of the Johnson Graph[J], Ars Combinatoria, Volume 100. 327-335. .