graph_square (791B)
1 # Graph square 2 3 [graph_exponentiation] by 2 of [undirected_graph] 4 5 Some are [Hamiltonian]: [graph_square_hamiltonian] 6 7 Three variants: 8 - connecting vertices with a distance *at most* two: this is the usual notion of graph square 9 - testing if an [undirected_graph] is a graph square in this sense is [NP_hard], cf [motwani1994computing] 10 - connecting vertices with a distance *exactly* two: studied in [bai2024characterizing] 11 - testing if an [undirected_graph] is a graph square in this sense is [PTIME] 12 - connecting vertices with a [walk] of length *exactly* two (but potentially also an edge): studied in [kutz2009digraph] 13 - testing if an [undirected_graph] is a graph square in this sense is [NP_hard] 14 15 Up: [graph_exponentiation] 16 17 See also: [radoszewski2011hamiltonian], [graph_cube]