Computing Graph Roots Without Short Cycles

Babak Farzad, Lap Chi Lau, Van Bang Le +1

Graph G is the square of graph H if two vertices x, y have an edge in G if and only if x, y are of distance at most two in H. Given H it is easy to compute its square H2, however M…