Papers › Inversion Diameter and Treewidth
Inversion Diameter and Treewidth
Yichen Wang, Haozhe Wang, Yuxuan Yang, Mei Lu
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
In an oriented graph G, the inversion of a subset X of vertices is the operation that reverses the orientation of all arcs with both end-vertices in X. The inversion graph of a graph G, denoted by ℐ(G), is the graph whose vertices are orientations of G in which two orientations G₁ and G₂ are adjacent if and only if there is an inversion transforming G₁ into G₂.The inversion diameter of a graph G is the diameter of its inversion graph ℐ(G), denoted by diam(ℐ(G)).Havet, H\"orsch, and Rambaud~(2024) first proved that for G of treewidth k, diam(ℐ(G)) ≤2k, and that there are graphs of treewidth k with inversion diameter k+2.In this paper, we construct graphs of treewidth k with inversion diameter $2k$, which implies that the previous upper bound diam(ℐ(G)) ≤2k is tight.Moreover, for graphs with maximum degree Δ, Havet, H\"orsch, and Rambaud~(2024) proved diam(ℐ(G)) ≤2Δ-1 and conjectured that diam(ℐ(G)) ≤Δ. We prove the conjecture when Δ=3 with the help of computer calculations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections