A density result for random sparse oriented graphs and its relation to a conjecture of Woodall
The electronic journal of combinatorics, Tome 9 (2002)
We prove that for all $\ell \ge 3$ and $\beta >0$ there exists a sparse oriented graph of arbitrarily large order with oriented girth $\ell$ and such that any $1/2 + \beta$ proportion of its arcs induces an oriented cycle of length $\ell$. As a corollary we get that there exist infinitely many oriented graphs with vanishing density of oriented girth $\ell$ such that deleting any $1/\ell$-fraction of their edges does not destroy all their oriented cycles. The proof is probabilistic.
@article{10_37236_1661,
author = {Jair Donadelli and Yoshiharu Kohayakawa},
title = {A density result for random sparse oriented graphs and its relation to a conjecture of {Woodall}},
journal = {The electronic journal of combinatorics},
year = {2002},
volume = {9},
doi = {10.37236/1661},
zbl = {1018.05042},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1661/}
}
TY - JOUR AU - Jair Donadelli AU - Yoshiharu Kohayakawa TI - A density result for random sparse oriented graphs and its relation to a conjecture of Woodall JO - The electronic journal of combinatorics PY - 2002 VL - 9 UR - http://geodesic.mathdoc.fr/articles/10.37236/1661/ DO - 10.37236/1661 ID - 10_37236_1661 ER -
%0 Journal Article %A Jair Donadelli %A Yoshiharu Kohayakawa %T A density result for random sparse oriented graphs and its relation to a conjecture of Woodall %J The electronic journal of combinatorics %D 2002 %V 9 %U http://geodesic.mathdoc.fr/articles/10.37236/1661/ %R 10.37236/1661 %F 10_37236_1661
Jair Donadelli; Yoshiharu Kohayakawa. A density result for random sparse oriented graphs and its relation to a conjecture of Woodall. The electronic journal of combinatorics, Tome 9 (2002). doi: 10.37236/1661
Cité par Sources :