On the $(\le p)$-inversion diameter of oriented graphs

Abstract

In an oriented graph $\vec{G}$, the {\it inversion} of a subset $X$ of vertices consists in reversing the orientation of all arcs with both endvertices in $X$. The {\it $(\le p)$-inversion graph} of a labelled graph $G$, denoted by ${\mathcal{I}}^{\le p}(G)$, is the graph whose vertices are the labelled orientations of $G$ in which two labelled orientations ${\vec{G}}_1$ and ${\vec{G}}_2$ of $G$ are adjacent if and only if there is a set $X$ with $|X|\le p$ whose inversion transforms ${\vec{G}}_1$ into ${\vec{G}}_2$. In this paper, we study the {\it $(\le p)$-inversion diameter} of a graph, denoted by ${\mathrm{id}}^{\le p}(G)$, which is the diameter of its $(\le p)$-inversion graph. We show that there exists a smallest number $\hat{I}{¨}_p$ with $\frac{1}{4}p-\frac{3}{2}\le \hat{I}{¨}_p\le \frac{1}{2}{p}^2$ such that ${\mathrm{id}}^{\le p}(G)\le \lceil \frac{|E(G)|}{\lfloor p/2\rfloor }\rceil +\hat{I}{¨}_p$ for all graph $G$. We then establish better upper bounds for several families of graphs and in particular trees and planar graphs. Let us denote by ${\mathrm{id}}_{\mathcal{F}}^{\le p}(n)$ (resp. ${\mathrm{id}}_{\mathcal{P}}^{\le p}(n)$) the maximum $(\le p)$-inversion diameter of a tree (resp. planar graph) of order $n$. For trees, we show ${\mathrm{id}}_{\mathcal{F}}^{\le 3}(n)=\lceil \frac{n-1}{2}\rceil$, ${\mathrm{id}}_{\mathcal{F}}^{\le 4}(n)=\frac{3}{8}n+\hat{I}˜(1)$, ${\mathrm{id}}_{\mathcal{F}}^{\le 5}(n)=\frac{2}{7}n+\hat{I}˜(1)$, and ${\mathrm{id}}_{\mathcal{F}}^{\le p}(n)\le \frac{n-1}{p-c\sqrt{p}}+2$ with $c=\sqrt{2+\sqrt{2}}$ for all $p\ge 6$. For planar graphs, we prove ${\mathrm{id}}_{\mathcal{P}}^{\le 3}(n)\le \frac{11n}{6}-\frac{8}{3}$, ${\mathrm{id}}_{\mathcal{P}}^{\le 4}(n)\le \frac{4n}{3}+\frac{10}{3}$, and ${\mathrm{id}}_{\mathcal{P}}^{\le p}(n)\le \lceil \frac{3n-6}{\lfloor p/2\rfloor }\rceil +8\lfloor p/2\rfloor -8$ for all $p\ge 6$.