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 $\text{diam}(I(G))$ is its diameter. Answering a question of Havet, Hörsch and Rambaud, we prove the bound in terms of edge number $\text{diam}(I(G))\le 2\sqrt{\mathrm{\mid }E(G)\mathrm{\mid }}$, and we complement it with a lower bound $\text{diam}(I(G))\ge \frac{\mathrm{\mid }E(G)\mathrm{\mid }}{\mathrm{\mid }V(G)\mathrm{\mid }}$ obtained by viewing $I(G)$ as a Cayley graph on ${\text{F}}_2^{E(G)}$. We further refine the upper bound for bipartite graphs $G$ by showing $\text{diam}(I(G))\le \max \{\rho ,\lceil {\log }_2(2+\sigma (2^{\rho -1}-1))\rceil \}$ where the two parts of $G$ have maximum degrees $\sigma$ and $\rho$, respectively.