Diameter of 2-distance graphs

Abstract

For a simple graph $G$, the $2$-distance graph, $D_2(G)$, is a graph with the vertex set $V(G)$ and two vertices are adjacent if and only if their distance is $2$ in the graph $G$. In this paper, for graphs $G$ with diameter 2, we show that $diam(D_2(G))$ can be any integer $t⩾2$. For graphs $G$ with $diam(G)⩾3$, we prove that $\frac{1}{2}diam(G)⩽diam(D_2(G))$ and this inequality is sharp. Also, for $diam(G)=3$, we prove that $diam(D_2(G))⩽5$ and this inequality is sharp.

10 pages, 15 figures. arXiv admin note: text overlap with arXiv:2306.15301, arXiv:2403.06132