Edge-Number Bounds for the Inversion Diameter of Graphs
The inversion of a set $X$ of vertices in an oriented graph reverses every arc with both endpoints in $X$. The inversion graph $I(G)$ of a graph $G$ has the labelled orientations of $G$ as its vertices, two orientations being adjacent when a single inversion transforms one into the other, and the inversion diameter $\diam(I(G))$ is its diameter. Answering a question of Havet, Hörsch and Rambaud, we prove the bound in terms of edge number $\diam(I(G)) \le 2\sqrt{|E(G)|}$, and we complement it with a lower bound $\diam(I(G)) \ge \frac{|E(G)|}{|V(G)|}$ obtained by viewing $I(G)$ as a Cayley…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.17974
curl -X POST /api/v1/records/arxiv/2606.17974/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.17974/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'