A density result for random sparse oriented graphs and its relation to a conjecture of Woodall

Donadelli, Jair; Kohayakawa, Yoshiharu

Advanced search

Search - Use quotation marks to get a more specific result

Index

Field of knowledge

Start date

Betweenand

(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

A density result for random sparse oriented graphs and its relation to a conjecture of Woodall

Full text
Author(s):	Donadelli, Jair ^[1] ; Kohayakawa, Yoshiharu ^[2] Total Authors: 2
Affiliation:	^[1] Univ Fed Parana, Dept Informat, Ctr Politecn, BR-81531990 Curitiba, Parana - Brazil ^[2] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo, SP - Brazil Total Affiliations: 2
Document type:	Journal article
Source:	ELECTRONIC JOURNAL OF COMBINATORICS; v. 9, 2002.
Web of Science Citations:	1
Abstract
We prove that for all l >= 3 and beta > 0 there exists a sparse oriented graph of arbitrarily large order with oriented girth l and such that any 1/2 + beta proportion of its arcs induces an oriented cycle of length l. As a corollary we get that there exist infinitely many oriented graphs with vanishing density of oriented girth l such that deleting any 1/l-fraction of their edges does not destroy all their oriented cycles. The proof is probabilistic. (AU)

FAPESP's process:	96/04505-2 - Structural and algorithmic aspects of combinatorial objects
Grantee:	Yoshiharu Kohayakawa
Support Opportunities:	Research Projects - Thematic Grants

Short URL