Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

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

Autor(es):
Donadelli, Jair [1] ; Kohayakawa, Yoshiharu [2]
Número total de Autores: 2
Afiliação do(s) autor(es):
[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
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: ELECTRONIC JOURNAL OF COMBINATORICS; v. 9, 2002.
Citações Web of Science: 1
Resumo

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)

Processo FAPESP: 96/04505-2 - Aspectos estruturais e algorítmicos de objetos combinatórios
Beneficiário:Yoshiharu Kohayakawa
Linha de fomento: Auxílio à Pesquisa - Temático