Connectivity 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, we characterize all graphs with connected 2-distance graph. For graphs with diameter 2, we prove that $D_2(G)$ is connected if and only if $G$ has no spanning complete bipartite subgraphs. For graphs with a diameter greater than 2, we define a maximal Fine set and by contracting $G$ on these subsets, we get a new graph $\hat{G}$ such that $D_2(G)$ is connected if and only if $D_2(\hat{G})$ is connected. Especially, $D_2(G)$ is disconnected if and only if $\hat{G}$ is bipartite.

arXiv comment7 pages, 6 figures