Characterizing and recognizing exact-distance squares of graphs

Abstract

For a graph $G=(V,E)$, its exact-distance square, $G^{[♯2]}$, is the graph with vertex set $V$ and with an edge between vertices $x$ and $y$ if and only if $x$ and $y$ have distance (exactly) $2$ in $G$. The graph $G$ is an exact-distance square root of $G^{[♯2]}$. We give a characterization of graphs having an exact-distance square root, our characterization easily leading to a polynomial-time recognition algorithm. We show that it is NP-complete to recognize graphs with a bipartite exact-distance square root. These two results strongly contrast known results on (usual) graph squares. We then characterize graphs having a tree as an exact-distance square root, and from this obtain a polynomial-time recognition algorithm for these graphs. Finally, we show that, unlike for usual square roots, a graph might have (arbitrarily many) non-isomorphic exact-distance square roots which are trees.

15 pages, 6 figures. References added and small changes according to referees' comments

References in corpus (2)

• Exact distance coloring in trees
• Exact square coloring of subcubic planar graphs

Cited by in corpus (1)

• Diameter Constraints in 2-distance Graphs