https://hal-cnrs.archives-ouvertes.fr/hal-03840741Bai, YandongYandongBaiCortes, PedroPedroCortesNaserasr, RezaRezaNaserasrIRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale - UPD7 - Université Paris Diderot - Paris 7 - CNRS - Centre National de la Recherche ScientifiqueQuiroz, DanileDanileQuirozCharacterizing and recognizing exact-distance squares of graphsHAL CCSD2022[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Naserasr, Reza2022-11-06 00:13:492022-11-09 04:09:062022-11-08 08:53:13enPreprints, Working Papers, ...application/pdf1For 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 exactdistance square roots which are trees.