
Let $D$ be an oriented graph. The inversion of a set $X$ of vertices in $D$ consists in reversing the direction of all arcs with both ends in $X$. The inversion number of $D$, denoted by ${\rm inv}(D)$, is the minimum number of inversions needed to make $D$ acyclic. Denoting by $\tau(D)$, $\tau' (D)$, and $\nu(D)$ the cycle transversal number, the cycle arc-transversal number and the cycle packing number of $D$ respectively, one shows that ${\rm inv}(D) \leq \tau' (D)$, ${\rm inv}(D) \leq 2\tau(D)$ and there exists a function $g$ such that ${\rm inv}(D)\leq g(\nu(D))$. We conjecture that for any two oriented graphs $L$ and $R$, ${\rm inv}(L\rightarrow R) ={\rm inv}(L) +{\rm inv}(R)$ where $L\rightarrow R$ is the dijoin of $L$ and $R$. This would imply that the first two inequalities are tight. We prove this conjecture when ${\rm inv}(L)\leq 1$ and ${\rm inv}(R)\leq 2$ and when ${\rm inv}(L) ={\rm inv}(R)=2$ and $L$ and $R$ are strongly connected. We also show that the function $g$ of the third inequality satisfies $g(1)\leq 4$. We then consider the complexity of deciding whether ${\rm inv}(D)\leq k$ for a given oriented graph $D$. We show that it is NP-complete for $k=1$, which together with the above conjecture would imply that it is NP-complete for every $k$. This contrasts with a result of Belkhechine et al. which states that deciding whether ${\rm inv}(T)\leq k$ for a given tournament $T$ is polynomial-time solvable.
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), mathematics - combinatorics, Limits and Structures in Graph Theory, Mathematical analysis, Graph, Transversal (combinatorics), Optical Code Division Multiple Access, Engineering, Graph Limits, QA1-939, FOS: Mathematics, FOS: Electrical engineering, electronic engineering, information engineering, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Conjecture, Electrical and Electronic Engineering, Physics, computer science - discrete mathematics, Computational Theory and Mathematics, Combinatorics, Computer Science, Physical Sciences, Combinatorics (math.CO), Mathematics, Computer Science - Discrete Mathematics, Graph Theory and Algorithms
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), mathematics - combinatorics, Limits and Structures in Graph Theory, Mathematical analysis, Graph, Transversal (combinatorics), Optical Code Division Multiple Access, Engineering, Graph Limits, QA1-939, FOS: Mathematics, FOS: Electrical engineering, electronic engineering, information engineering, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Conjecture, Electrical and Electronic Engineering, Physics, computer science - discrete mathematics, Computational Theory and Mathematics, Combinatorics, Computer Science, Physical Sciences, Combinatorics (math.CO), Mathematics, Computer Science - Discrete Mathematics, Graph Theory and Algorithms
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
