2025/01/02 by Al-saadi, Oleksiy, Natal, Joseph
#68R10 #Combinatorics (math.CO) #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2501.01575
For any finite, simple graph G = (V,E), its 2-distance graph G2 is a graph having the same vertex set V where two vertices are adjacent if and only if their distance is 2 in G. Connectivity and diameter properties of these graphs have been well studied. For example, it has been shown that if \rm diam(G) = k ≥ 3 then \lceil (1)/(2) k \rceil ≤ \rm diam(G2), and that this bound is sharp. In this paper, we prove that \rm diam(G2) = ∞ (that is, G2 is disconnected) or otherwise \rm diam(G2) ≤ k + 2. In addition, we show that this inequality is sharp for any even k, a result that we verify for some higher orders through judicious use of a sat solver.