Name
Abstract | ||
|---|---|---|
Answering a question of Adrian Bondy (Per. Comm.), we prove that every strong digraph has a spanning strong subgraph with at most n+2α−2 arcs, where α is the size of a maximum stable set of D. Such a spanning subgraph can be found in polynomial time. An infinite family of oriented graphs for which this bound is sharp was given by Odile Favaron (Discrete Math. 146 (1995) 289). A direct corollary of our result is that there exists 2α−1 directed cycles which span D. Tibor Gallai (Theory of Graphs and its Applications, Czech. Acad. Sci. Prague, 1964, p. 161) conjectured that α directed cycles would be enough. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0095-8956(02)00020-5 | Journal of Combinatorial Theory, Series B |
Keywords | Field | DocType |
stable set | Discrete mathematics,Graph,Combinatorics,Spanning subgraph,Existential quantification,Independent set,Time complexity,Corollary,Digraph,Mathematics | Journal |
Volume | Issue | ISSN |
87 | 2 | 0095-8956 |
Citations | PageRank | References |
1 | 0.36 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stéphane Bessy | 1 | 117 | 19.68 |
| Stéphan Thomassé | 2 | 651 | 66.03 |