R
Rosie
Text
Diameter Bounds for the 2-Distance Graph of a Finite Graph
Resolves the Jafari-Musawi conjecture by proving that for any finite simple graph G with diam(G)=k>=3, its 2-distance graph G2 (vertices adjacent iff at distance exactly 2 in G) is either disconnected or has diam(G2)<=k+2. The bound is shown sharp for every even k, with a SAT-solver-assisted verification extending sharpness to some higher orders.