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, i is an element of{1, 2}. We determine, for all pairs of nonnegative 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 (for i is an element of{1, 2}) has at least k(i) (out-) neighbours in V3-i. We prove that it is 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 of the structure of NP-complete instances in terms of their strong component digraph. When we want higher indegree or out-degree to/from the other set, the problem becomes NP-complete even for strong digraphs. A further result is that it is 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 | DOI | Venue |
|---|---|---|
2019 | 10.1002/jgt.22444 | JOURNAL OF GRAPH THEORY |
Keywords | DocType | Volume |
eulerian,minimum out-degree,2-partition,spanning bipartite subdigraph,strong spanning subdigraph | Journal | 92 |
Issue | ISSN | Citations |
2 | 0364-9024 | 0 |
PageRank | References | Authors |
0.34 | 4 | 5 |
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 |
| Anders Yeo | 5 | 1225 | 108.09 |