Geodesic
Covering small subgraphs of (hyper)tournaments with spanning acyclic subgraphs
The electronic journal of combinatorics, Tome 27 (2020) no. 4

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl DOI
While the edges of every tournament can be covered with two spanning acyclic subgraphs, this is not so if we set out to cover all acyclic $H$-subgraphs of a tournament with spanning acyclic subgraphs, even for very simple $H$ such as the $2$-edge directed path or the $2$-edge out-star. We prove new bounds for the minimum number of elements in such coverings and for some $H$ our bounds determine the exact order of magnitude. A $k$-tournament is an orientation of the complete $k$-graph, where each $k$-set is given a total order (so tournaments are $2$-tournaments). As opposed to tournaments, already covering the edges of a $3$-tournament with the minimum number of spanning acyclic subhypergraphs is a nontrivial problem. We prove a new lower bound for this problem which asymptotically matches the known lower bound of covering all ordered triples of a set.
DOI : 10.37236/9336
Classification : 05C70, 05C20, 05C35
Mots-clés : \(k\)-tournament 
Raphael Yuster. Covering small subgraphs of (hyper)tournaments with spanning acyclic subgraphs. The electronic journal of combinatorics, Tome 27 (2020) no. 4. doi: 10.37236/9336
@article{10_37236_9336,
     author = {Raphael Yuster},
     title = {Covering small subgraphs of (hyper)tournaments with spanning acyclic subgraphs},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {4},
     doi = {10.37236/9336},
     zbl = {1450.05071},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9336/}
}
TY  - JOUR
AU  - Raphael Yuster
TI  - Covering small subgraphs of (hyper)tournaments with spanning acyclic subgraphs
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9336/
DO  - 10.37236/9336
ID  - 10_37236_9336
ER  - 
%0 Journal Article
%A Raphael Yuster
%T Covering small subgraphs of (hyper)tournaments with spanning acyclic subgraphs
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/9336/
%R 10.37236/9336
%F 10_37236_9336

Cité par Sources :