Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650564 | Discrete Mathematics | 2008 | 4 Pages |
Abstract
Hoàng–Reed conjecture asserts that every digraph DD has a collection CC of circuits C1,…,Cδ+C1,…,Cδ+, where δ+δ+ is the minimum outdegree of DD, such that the circuits of CC have a forest-like structure. Formally, |V(Ci)∩(V(C1)∪⋯∪V(Ci-1))|⩽1|V(Ci)∩(V(C1)∪⋯∪V(Ci-1))|⩽1, for all i=2,…,δ+i=2,…,δ+. We verify this conjecture for the class of tournaments.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Frédéric Havet, Stéphan Thomassé, Anders Yeo,