Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

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 exactdistance square roots which are trees.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Reza Naserasr Connect in order to contact the contributor
Submitted on : Sunday, November 6, 2022 - 12:13:49 AM
Last modification on : Wednesday, November 9, 2022 - 4:09:06 AM


exact_squares_01Nov 2022-submi...
Files produced by the author(s)


  • HAL Id : hal-03840741, version 1



Yandong Bai, Pedro Cortes, Reza Naserasr, Danile Quiroz. Characterizing and recognizing exact-distance squares of graphs. {date}. ⟨hal-03840741⟩



Record views


Files downloads