Inversion Diameter and Treewidth

An orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph. Let $G$ be a simple graph and $\overrightarrow{G_{1}}$ an orientation of $G$. If $X$ is a vertex set of $G$, the inversion of $X$ on $\overrightarrow{G_{1}}$ is a orientation $\overrightarrow{G_{2}}$ by reversing the orientation of all arcs with both ends in $X$.

The concept of inversion was first introduced by Belkhechine et al. [4]. They studied the inversion number of a directed graph $D$, denoted by $inv(D)$, which is the minimum number of inversions that transform $D$ into an acyclic graph. They proved, for every fixed $k$, given a tournament $T$, determining whether $inv(T)\leq k$ is polynomial-time solvable. In contrast, Bang-Jensen et al. [3] proved that given any directed graph $D$, determining whether $inv(D)\leq 1$ is NP-complete.

The maximum inversion numbers of all oriented graphs of order $n$, denoted by $inv(n)$, has also been investigated. Aubian et al. [2] and Alon et al. [1] proved $n-2\sqrt{2\log n}\leq inv(n)\leq n-\lceil\log(n+1)\rceil$. Besides these results, various related questions have also been studied.

Let $G$ be a simple graph. The inversion is a transformation between different orientations of $G$. Instead of transforming an orientation into an acyclic orientation, it is also natural to consider the transformation between two orientations. The inversion graph of $G$ denoted by $\mathcal{I}(G)$, is the graph whose vertices are the orientations of $G$ in which two orientations $\overrightarrow{G_{1}}$ and $\overrightarrow{G_{2}}$ are adjacent if and only if there is an inversion $X$ transforming $\overrightarrow{G_{1}}$ into $\overrightarrow{G_{2}}$. The inversion diameter of $G$ is the diameter of $\mathcal{I}(G)$, denoted by $diam(\mathcal{I}(G))$. It represents the maximum number of required inversions to transform an orientation of $G$ into another orientation of it.

Havet et al. [5] first introduced inversion diameter and studied it on various class of graphs. Let $G$ be a graph and let $<$ be a total ordering on $V(G)$. For every pair $u,u^{\prime}$ of vertices in $G$, let $N_{<u^{\prime}}(u)=\{v\in N(u)\mid v<u^{\prime}\}$ and $N_{>u^{\prime}}(u)=\{v\in N(u)\mid v>u^{\prime}\}$. We simply write $N_{<}(u)$ for $N_{<u}(u)$ and $N_{>}(u)$ for $N_{>u}(u)$. The ordering $<$ is $t$-strong if for every $u\in V(G)$

• •

  $|N_{<}(u)|+\log(|\{X\subseteq V(G)\mid\exists v\in N_{>}(u),X\subseteq N_{<u}(v)\}|)<t$, if $N_{>}(u)\neq\emptyset$, and

• •

  $N_{<}(u)\leq t$ otherwise.

A graph is strongly $t$-degenerate if it admits a $t$-strong ordering of its vertices. Havet et al. [5] showed that

With the help of Theorem 1.1, they showed various bounds on $diam(\mathcal{I}(G))$ depending on the structure of $G$ as following:

Havet et al. [5] also proved that for fixed $k\geq 2$, given a graph $G$, determining whether $diam(\mathcal{I}(G))\leq k$ is NP-hard. For a graph $G$ with maximum degree $3$ (sub-cubic graph), Havet et al. [5] showed a better bound $diam(\mathcal{I}(G))\leq 4$. Moreover, they proposed a conjecture on graphs with maximum degree $\Delta$ as Conjecture 1.3.

The conjecture is true for $\Delta\leq 2$ [5]. In this paper, we prove the conjecture when $\Delta=3$. Computer assistance will be used in the proof of Theorem 1.4. A pure mathematical proof is still worth studying.

For graphs with treewidth at most $k$, Havet et al. [5] showed that there are graphs of treewidth at most $k$ with inversion diameter $k+2$. In this paper, we show that the upper bound $diam(\mathcal{I}(G))\leq 2k$ for graphs of treewidth at most $k$ is tight by proving Theorem 1.5. It answers a question proposed by Havet et al. in [5].

This paper is organized as follows. In Section 2, we give basic definitions and notation. The proofs of Theorems 1.5 and 1.4 are given in Sections 3 and 4, respectively.

Let $G=(V,E)$ be a graph. The distance between $u$ and $v$, denoted by $dist(u,v)$, is the number of edges in a shortest path joining $u$ and $v$. For any vertex $u\in V(G)$, denote $N(u)=\{v~{}|~{}uv\in E(G)\}$. Then $d(u)=|N(u)|$ is the degree of $u$. Let $\Delta=\Delta(G)$ be the maximum degree of $G$. We call $G$ $k$-regular if $d(u)=k$ for any $u\in V(G)$. Let $G$ be a graph and $S$ a vertex subset. Let $G[S]$ denote the subgraph of $G$ induced by $S$. For a graph $G$ and a vertex $v$, denote $G-v$ the graph induced by $V(G)-\{v\}$. For a graph $G$ and a induced subgraph $H$, denote $G-H$ the graph induced by $V(G)-V(H)$.

A label of $G$ is a mapping $\pi:E(G)\rightarrow\mathbb{F}_{2}$. A $t$-dim vector assignment of $G$ with the label $\pi$ is a mapping $f:V(G)\rightarrow\mathbb{F}_{2}^{t}$ such that $\pi(uv)=f(u)\cdot f(v)$ for every edge $uv\in E(G)$, where $f(u)\cdot f(v)$ to be the scalar product of $f(u)$ and $f(v)$ over $\mathbb{F}_{2}^{t}$. Usually, we use bold letter $\mathbf{u}$ to represent $f(u)$. We use $\mathbf{0}$  (resp. $\mathbf{1}$) to represent vectors in $\mathbb{F}_{2}^{t}$ whose coordinates are all $0$ (resp. $1$). We say a vector $\mathbf{u}\in\mathbb{F}_{2}^{t}$ is odd (resp. even), if $\mathbf{u\cdot 1}$ is one  (resp. zero), i.e., $\mathbf{u}$ has odd (resp. even) number of $1$.

The inversion diameter has a close relationship with vector assignment as following.

The treewidth of a graph $G$ is denoted by $tw(G)$. There are many ways to define treewidth. Here we give a definition of treewidth from the perspective of $k$-tree.

We say a graph is a partial $k$-tree if it is a subgraph of a $k$-tree. It is known that a graph $G$ is a partial $k$-tree, if and only if the treewidth of $G$ is at most $k$ [6, 7].

Let $\mathcal{L}(\mathbf{v_{1},\ldots,v_{k}})$ denote the linear space spanned by $\mathbf{v_{1},\ldots,v_{k}}$. For two vectors $\mathbf{v}$ and $\mathbf{u}$ in $\mathbb{F}_{2}^{t}$, we write $\mathbf{v\perp u}$ if $\mathbf{v\cdot u}=0$. For a vector $\mathbf{v}\in\mathbb{F}_{2}^{t}$ and a linear space $\mathbf{U}$ in $\mathbb{F}_{2}^{t}$, we write $\mathbf{v\perp U}$ if $\mathbf{v\perp u}$ for any $\mathbf{u\in U}$. The orthogonal complementary space of $\mathbf{U}$ is $\mathbf{U}^{\perp}=\{\textbf{v}\mid\mathbf{v\perp U}\}$. For any positive integer $k$, write $[k]=\{1,2,\ldots,k\}$.

Let $\mathbf{U}$ be a self-orthogonal linear space. Then $\mathbf{U}$ is orthogonal and every vector in $\mathbf{U}$ is even. It is easy to verify that $\mathbf{U}$ is self-orthogonal if and only if it has self-orthogonal base vectors.

For a linear space $\mathbf{U}$ and a vector $\mathbf{v}$, denote $\mathbf{v+U}$ by the set $\{\mathbf{v+u}\mid\mathbf{u\in U}\}$ and denote $\mathcal{L}(\mathbf{U,v})$ the space spanned by $\mathbf{v}$ and a basis of $\mathbf{U}$, that is the summation space of $\mathbf{U}$ and $\mathcal{L}(\mathbf{v})$.

For $k\geq 1$, we define a sequence of graph $G_{i}^{(k)}$ with a fixed label $\pi_{i}^{(k)}$. First, let $G_{0}^{(k)}$ be a $k$-clique with an arbitrarily label $\pi_{0}^{(k)}$. Then, we recursively construct $G_{i}^{(k)}$ as following:

(i) for each $k$-clique with vertices $v_{1},\ldots,v_{k}$ in $G_{i-1}^{(k)}$ and each $\mathbf{x}=(x_{1},\ldots,x_{k})^{T}\in\mathbb{F}_{2}^{k}$, we add a new vertex $u$ such that $uv_{j}\in E(G_{i}^{(k)})$ and $\pi_{i}^{(k)}(uv_{j})=x_{j}$, for all $1\leq j\leq k$ ;

(ii) $\pi^{(k)}_{i}|_{G^{(k)}_{i-1}}=\pi^{(k)}_{i-1}$.

Since $|\mathbb{F}_{2}^{k}|=2^{k}$, we add $2^{k}$ new vertices for each $k$-clique in $G_{i-1}^{(k)}$. By Definition 2.2, $G_{m}^{(k)}$ is a $k$-tree for any $m$, that is, of treewidth at most $k$. Since $\pi^{(k)}_{n}|_{G^{(k)}_{m}}=\pi^{(k)}_{m}$ when $n>m$, we may use $\pi^{(k)}$ to denote the label of $G^{(k)}_{m}$ for any $m$. For any vertex $v\in V(G^{(k)}_{m})$ with $m\geq 1$, there exists an unique $n$ such that $v\in V(G^{(k)}_{n})-V(G^{(k)}_{n-1})$. We say $n$ is the level of $v$, denoted by $l(v)=n$. For a vertex set $S\subseteq G^{(k)}_{m}$ with $m\geq 1$, the level of $S$ is defined to be the maximum level of vertices in $S$ denoted by $l(S)$, that is, $l(S)=\max\limits_{v\in S}\{l(v)\}$. Clearly, if $v$ is a vertex in $G_{m}^{(k)}$, then $l(v)\leq m$. Similarly, if $C$ is a vertex set in $G_{m}^{(k)}$, then $l(C)\leq m$.

Note that if $H$ is a subgraph of $G$, then $diam(\mathcal{I}(H))\leq diam(\mathcal{I}(G))$. So $(diam(\mathcal{I}(G_{m}^{(k)})))_{m\geq 0}$ is an increasing sequence with upper bound $2k$ by Theorem 1.2.

Let $\lambda^{(k)}=\lim\limits_{m\rightarrow+\infty}diam(\mathcal{I}(G_{m}^{(k)}))$. Then $\lambda^{(k)}\leq 2k$. We will show that $\lambda^{(k)}=2k$ and then $G_{m}^{(k)}$ is of inversion diameter $2k$ when $m$ is sufficiently large.

Next we suppose $\lambda^{(k)}\leq 2k-1$. Then for any $m$, $G_{m}^{(k)}$ has a $(2k-1)$-dim vector assignment with the label $\pi^{(k)}$ by Proposition 2.1. Thus for each $v\in V(G_{m}^{(k)})$, there is a vector $\mathbf{v}\in\mathbb{F}_{2}^{2k-1}$ corresponding to it. The following lemmas show the properties of the vectors assigned to $k$-cliques in $G^{(k)}_{m}$.

The above lemmas actually work for arbitrary $\lambda^{(k)}$. The following lemmas need the assumption $\lambda^{(k)}\leq 2k-1$. If $\mathbf{b=0}$, we have a strong conclusion.

For each $j\in[k]$, the solution set of $\mathbf{Ax=Av_{j}}$ is in $\mathbf{v_{j}+U}\subseteq\mathcal{L}(\mathbf{v_{1}},\ldots,\mathbf{v_{k}})$. By Lemma 3.3, $\sum_{i=1}^{k}\mathbf{v_{i}}\in\mathbf{v_{j}+U}$. Therefore, $\mathbf{v_{j}\in U}$ for any $1\leq j\leq k$, which contradicts that $dim(\mathbf{U})=k-1$ because $\mathbf{v_{1}},\ldots,\mathbf{v_{k}}$ are linear independent. $\square$

Note that a single vertex is always a bad $1$-clique. If $\lambda^{(k)}\leq 2k-1$, “large” bad clique will finally cause contradictions. The following lemma is the main part of our proof which states that we can find “large” bad clique when $m$ is sufficiently large.

We first show that $dim(\textbf{U})=p-1$. Suppose $dim(\textbf{U})=p$. Then $\textbf{U}=\textbf{V}_{C_{1}}\subseteq\textbf{V}_{C_{1}}^{\perp}$. Since $p<k$, by the construction of $G^{(k)}_{m+k+2}$, there exists a vertex $u$ of level $m+1$ such that $uv_{i}\in E(G^{(k)}_{m+k+2})$ and $\pi^{(k)}(uv_{i})=0$ for each $i\in[p]$. Let $C_{2}\coloneqq{C_{1}}\cup\{u\}$. By Lemma 3.1, we have $\mathbf{u,v_{1},\ldots,v_{p}}$ are linear independent. By $\pi^{(k)}(uv_{i})=0$ for each $i\in[p]$, we have that $\mathbf{u\perp V_{C_{1}}}$. Thus $\textbf{V}_{C_{1}}\subseteq\textbf{V}_{C_{2}}\cap\textbf{V}_{C_{2}}^{\perp}$ which implies $dim(\textbf{V}_{C_{2}}\cap\textbf{V}_{C_{2}}^{\perp})\geq p$. Hence $C_{2}$ is a bad $(p+1)$-clique, a contradiction with the maximality of ${C_{1}}$. So $dim(\textbf{U})=p-1$. In fact, we conclude that U is a self-orthogonal $(p-1)$-dim subspace of $\mathbb{F}_{2}^{2k-1}$ and then each vector in U is even.

Since $dim(\textbf{U})=p-1$, there is $\textbf{v}_{i}\in\{\textbf{v}_{1},\textbf{v}_{2},\dots,\textbf{v}_{p}\}$, say $i=1$, such that $\textbf{v}_{1}\notin\textbf{U}$. Then $\mathcal{L}(\textbf{U},\textbf{v}_{1})=\textbf{V}_{C_{1}}$. If $\mathbf{v_{1}}$ is even, then $\mathbf{v_{1}}\perp\mathcal{L}(\textbf{U},\textbf{v}_{1})$, which contradicts with $\mathbf{v_{1}}\notin\textbf{U}$. Thus we have $\textbf{v}_{1}$ is odd.

Fix a vertex $v_{0}$ of level $m+1$ such that $v_{0}v_{i}\in E(G^{(k)}_{m+k})$ and $\pi^{(k)}(v_{0}v_{i})=0$ for each $i\in[p]$. Then $\mathbf{v}_{0}\perp\mathbf{V_{C_{1}}}$. By the construction of $G^{(k)}_{m+k}$, there exists a set of vertices $C_{2}=\{w_{1},w_{2},\dots,w_{k-p}\}\subseteq V(G^{(k)}_{m+k})$ satisfying the following:

1. 1.

   $\{v_{0},v_{1},\ldots,v_{p},w_{1},w_{2},\ldots,w_{k-p}\}$ is a $(k+1)$-clique;

2. 2.

   $\pi^{(k)}(w_{i}w_{j})=0$, for each $i,j\in[k-p],i\neq j$;

3. 3.

   and $\pi^{(k)}(v_{i}w_{j})=\textbf{v}_{i}\cdot(\textbf{v}_{1}+\textbf{v}_{0})$, for each $i\in[0,p],j\in[k-p]$.

Now we complete the proof of Lemma 3.6. For each $j\in[k-p]$, let $\beta_{j}=\textbf{v}_{0}+\textbf{v}_{1}+\textbf{w}_{j}$. By Claim 3.7, $\textbf{v}_{0}$ is odd. By Claim 3.8, $\textbf{w}_{j}$ is even for each $j\in[k-p]$. It is not difficult to show that $\beta_{j}\perp\textbf{v}_{0}$, $\beta_{j}\perp\textbf{V}_{C_{1}}$ and $\beta_{j}\perp\textbf{V}_{C_{2}}$. Check Table 1 for the inner products between the vectors that we are working on. Let $C_{3}=C_{1}\cup C_{2}$ and $W=\textbf{V}_{C_{3}}=\textbf{V}_{C_{1}}+\textbf{V}_{C_{2}}$. Then $dim(W)=k$ from Lemma 3.1. Since $W\subseteq\mathbb{F}_{2}^{2k-1}$, we have $dim(W^{\perp})=k-1$. Let $W^{\prime}=\mathcal{L}(\textbf{U},\beta_{1},\dots,\beta_{k-p})$. Since $\textbf{U}\perp W$ and $\beta_{j}\perp W$ for each $j\in[k-p]$, we have $W^{\prime}\subseteq W^{\perp}$. Note that $\textbf{V}_{C_{1}},\textbf{V}_{C_{2}}\subseteq\mathcal{L}(\textbf{v}_{0},\textbf{v}_{1},W^{\prime})$. We have $W\subseteq\mathcal{L}(\textbf{v}_{0},\textbf{v}_{1},W^{\prime})$ which implies $dim(W^{\prime})\geq k-2$. If $\textbf{v}_{0}\notin W$, then $dim(W^{\prime})\geq k-1$ which implies $W^{\perp}=W^{\prime}$. Since $\textbf{v}_{0}\perp W^{\prime}$, we have $\textbf{v}_{0}\perp W^{\perp}$, a contradiction with $\textbf{v}_{0}\notin W$. Hence $\textbf{v}_{0}\in W$. By Lemma 3.2, we have $\textbf{v}_{0}+\dots+\textbf{v}_{p}+\textbf{w}_{1}+\dots+\textbf{w}_{k-p}=0$.

Since $\textbf{v}_{0}\in W$, we have $\beta_{j}\in W$ for each $j$ which implies $W^{\prime}\subseteq W$. So $W^{\prime}\subseteq W\cap W^{\perp}$. If $dim(W^{\prime})\geq k-1$, then $C_{3}$ is a bad $k$-clique, a contradiction with the maximality of $C_{1}$. Hence $dim(W^{\prime})=k-2$. Let $\alpha\in W^{\perp}\backslash W^{\prime}$ such that $W^{\perp}=\mathcal{L}(W^{\prime},\alpha)$. By the construction of $G^{(k)}_{m+k}$, there exists a vertex $x$ connecting to all vertices of $C_{3}$ such that $\pi^{(k)}(xy)=0$ for each $y\in C_{3}$. Then $\textbf{x}\in W^{\perp}$. From Claim 3.7, x is odd. Since U is a self-orthogonal subspace and $\beta_{i}\bot\beta_{j}$ for any $i,j\in[k-p]$ (see Table 1), we have that the vectors in $W^{\prime}$ are all even. By $\textbf{x}\in W^{\perp}=\mathcal{L}(W^{\prime},\alpha)$ and x being odd, we have $\alpha$ is odd.

Let $C^{*}=\{v_{0},\ldots,v_{p},w_{1},\ldots,w_{k-p-1}\}$ (if $p=k-1$, then let $C^{*}=\{v_{0},\ldots,v_{p}\}$). Then there is $x^{*}$ connecting to all vertices of $C^{*}$ such that $\pi^{(k)}(x^{*}y)=\textbf{v}_{0}\cdot\textbf{y}$ for each $y\in C^{*}$. Since $\textbf{v}_{0}+\dots+\textbf{v}_{p}+\textbf{w}_{1}+\dots+\textbf{w}_{k-p}=0$, by Lemma 3.1, $W=\textbf{V}_{C^{*}}$. Then $\textbf{x}^{*}\in\textbf{v}_{0}+W^{\perp}$. Since $\pi^{(k)}(x^{*}v_{i})=\textbf{v}_{0}\cdot\textbf{v}_{i}=0$ for each $i\in[k]$, from Claim 3.7, $\textbf{x}^{*}$ is odd. Note that $\textbf{x}^{*}\in\textbf{v}_{0}+\mathcal{L}(\alpha,W^{\prime})$. Since all vectors in $W^{\prime}$ are even and $\textbf{v}_{0},\alpha$ are odd, we have $\textbf{x}^{*}\in\textbf{v}_{0}+W^{\prime}\subseteq W$. From Lemma 3.2, $\textbf{x}^{*}=\textbf{v}_{0}+\dots+\textbf{v}_{p}+\textbf{w}_{1}+\dots+\textbf{w}_{k-p-1}=\textbf{w}_{k-p}$. Since $\textbf{x}^{*}\cdot\mathbf{v_{1}}=0\neq 1=\textbf{w}_{k-p}\cdot\mathbf{v_{1}}$ , we derive a contradiction. $\square$