commit f377ef369f5d55b60c7bfb26b79d5a7e1970bce3
parent d3efee04449f0f689efe8048f488155cda88d823
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 11 Dec 2025 14:06:59 +0100
commit with codex
Diffstat:
10 files changed, 57 insertions(+), 12 deletions(-)
diff --git a/graph_exact_distance_square b/graph_exact_distance_square
@@ -0,0 +1,9 @@
+# Graph exact distance square
+
+Given a [graph] G, the *exact square* of G is a graph G' on the same [vertices] where you connect each pair of vertices that are connected by a [walk] of length exactly 2
+
+[graph_exact_distance_square_root_problem]
+
+Up: [graph_square]
+
+See also: [Graph_exact_square]
diff --git a/graph_exact_distance_square_root_problem b/graph_exact_distance_square_root_problem
@@ -0,0 +1,10 @@
+# Graph exact distance square root problem
+
+The [computational_problem], given an [undirected_graph] G, of deciding whether G is the [graph_exact_distance_square] of some graph G'
+
+studied in [bai2024characterizing]: it is [PTIME]
+- however, if you want to know whether a [graph_bipartite] G' exists, then it is [NP_hard]
+
+Up: [graph_exact_distance_square]
+
+See also: [graph_exact_square_root_problem], [graph_square_root_problem]
diff --git a/graph_exact_square b/graph_exact_square
@@ -0,0 +1,9 @@
+# Graph exact square
+
+Given a [graph] G, the *exact square* of G is a graph G' on the same [vertices] where you connect each pair of vertices that are connected by a [walk] of length exactly 2
+
+[graph_exact_square_root_problem]
+
+Up: [graph_square]
+
+See also: [graph_square_root], [graph_exact_distance_square]
diff --git a/graph_exact_square_root_problem b/graph_exact_square_root_problem
@@ -0,0 +1,9 @@
+# Graph exact square root problem
+
+The [computational_problem], given an [undirected_graph] G, of deciding whether G is the [graph_exact_square] of some graph G'
+
+Studied in [kutz2009digraph]: this is [NP_hard]
+
+Up: [graph_exact_square]
+
+See also: [Graph_exact_distance_square_root_problem]
diff --git a/graph_hamiltonian b/graph_hamiltonian
@@ -6,6 +6,6 @@ For the [recognition_problem], see [Hamiltonian_path_problem]
Up: [graph_family]
-Aliases: Hamiltonian graph, Hamiltonian graphs
+Aliases: Hamiltonian graph, Hamiltonian graphs, Hamiltonian
See also: [hamiltonian_connected_graph]
diff --git a/graph_square b/graph_square
@@ -6,12 +6,10 @@ Some are [Hamiltonian]: [graph_square_hamiltonian]
Three variants:
- connecting vertices with a distance *at most* two: this is the usual notion of graph square
- - testing if an [undirected_graph] is a graph square in this sense is [NP_hard], cf [motwani1994computing]
-- connecting vertices with a distance *exactly* two: studied in [bai2024characterizing]
- - testing if an [undirected_graph] is a graph square in this sense is [PTIME]
-- connecting vertices with a [walk] of length *exactly* two (but potentially also an edge): studied in [kutz2009digraph]
- - testing if an [undirected_graph] is a graph square in this sense is [NP_hard]
+ - [graph_square_root_problem]
+- connecting vertices with a [walk] of length *exactly* two (but potentially also an edge): this is [graph_exact_square]
+- connecting vertices with a distance *exactly* two: this is [graph_exact_distance_square]
Up: [graph_exponentiation]
-See also: [radoszewski2011hamiltonian], [graph_cube]
+See also: [radoszewski2011hamiltonian], [graph_cube], [graph_square_root], [graph_exact_square]
diff --git a/graph_square_root_problem b/graph_square_root_problem
@@ -0,0 +1,7 @@
+# Graph square root problem
+
+The [computational_problem], given an [undirected_graph] G, of deciding whether G is the [graph_square] of some graph G'
+
+It is [NP_hard], cf [motwani1994computing]
+
+Up: [computational_problem], [graph_square]
diff --git a/hamiltonian_connected_graph b/hamiltonian_connected_graph
@@ -4,6 +4,6 @@ An [undirected_graph] where for any pair of distinct [vertices] there is a [Hami
The [decision_problem] of recognizing them is [NP_complete], see [jedlickova2025hamiltonian]
-See also: [graph_hamiltonian]
+See also: [graph_hamiltonian], [Radoszewski2011hamiltonian]
Up: [graph]
diff --git a/hamiltonian_cycle_square b/hamiltonian_cycle_square
@@ -1,5 +1,8 @@
# Hamiltonian cycle square
-see [radoszewski2011hamiltonian]
+On [graphs], it is [NP_hard] to determine if the [graph_square] of an input [graph] is [hamiltonian]
+- cf https://en.wikipedia.org/wiki/Graph_power#Computational_complexity
+
+On [trees], see [radoszewski2011hamiltonian]
Up: [hamiltonian_cycle], [graph_square]
diff --git a/radoszewski2011hamiltonian b/radoszewski2011hamiltonian
@@ -2,10 +2,10 @@
Studies when the [graph_square] of an [undirected_graph] has [Hamiltonian_cycle] and [Hamiltonian_path]
-[harary1971trees] shows that [graph_square] of [tree] contains a [Hamiltonian_cycle] iff it is a [caterpillar_tree]
+[harary1971trees] shows that [graph_square] of a [tree] contains a [Hamiltonian_cycle] iff it is a [caterpillar_tree]
-They show that [graph_square] of [tree] contains a [Hamiltonian_path] iff it is a [horsetail_graph]. Testing this, and finding the path, can be done in [linear_time], and [linear_time] [preprocessing] is sufficient to test in constant time, given (u, v), whether there is a [Hamiltonian_path] from u to v.
+They show that the [graph_square] of a [tree] contains a [Hamiltonian_path] iff it is a [horsetail_graph]. Testing this, and finding the path, can be done in [linear_time], and [linear_time] [preprocessing] is sufficient to test in constant time, given (u, v), whether there is a [Hamiltonian_path] from u to v.
Up: [academic_paper] on [hamiltonian_cycle]
-See also: [hamiltonian_cycle_square], [hamiltonian_cycle_cube]
+See also: [hamiltonian_cycle_square], [hamiltonian_cycle_cube], [Hamiltonian_connected_graph]
