Name
Abstract | ||
|---|---|---|
For a given $2$-partition $(V_1,V_2)$ of the vertices of a (di)graph $G$, we study properties of the spanning bipartite subdigraph $B_G(V_1,V_2)$ of $G$ induced by those arcs/edges that have one end in each $V_i$. We determine, for all pairs of non-negative integers $k_1,k_2$, the complexity of deciding whether $G$ has a 2-partition $(V_1,V_2)$ such that each vertex in $V_i$ has at least $k_i$ (out-)neighbours in $V_{3-i}$. We prove that it is ${cal NP}$-complete to decide whether a digraph $D$ has a 2-partition $(V_1,V_2)$ such that each vertex in $V_1$ has an out-neighbour in $V_2$ and each vertex in $V_2$ has an in-neighbour in $V_1$. The problem becomes polynomially solvable if we require $D$ to be strongly connected. We give a characterisation, based on the so-called strong component digraph of a non-strong digraph of the structure of ${cal NP}$-complete instances in terms of their strong component digraph. When we want higher in-degree or out-degree to/from the other set the problem becomes ${cal NP}$-complete even for strong digraphs. A further result is that it is ${cal NP}$-complete to decide whether a given digraph $D$ has a $2$-partition $(V_1,V_2)$ such that $B_D(V_1,V_2)$ is strongly connected. This holds even if we require the input to be a highly connected eulerian digraph. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Discrete Mathematics | Integer,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Bipartite graph,Eulerian path,Strongly connected component,Mathematics,Digraph |
DocType | Volume | Citations |
Journal | abs/1707.09400 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jørgen Bang-Jensen | 1 | 573 | 68.96 |
| Stéphane Bessy | 2 | 117 | 19.68 |
| Frédéric Havet | 3 | 433 | 55.15 |
| Anders Yeo | 4 | 1225 | 108.09 |