EVEN CYCLES IN DIRECTED-GRAPHS

Authors
CHUNG FRK GODDARD W KLEITMAN DJ
Citation
Frk. Chung et al., EVEN CYCLES IN DIRECTED-GRAPHS, SIAM journal on discrete mathematics, 7(3), 1994, pp. 474-483
Citations number
21
Categorie Soggetti
Mathematics,Mathematics
Journal title
SIAM journal on discrete mathematics → ACNP
ISSN journal
08954801
Volume
7
Issue
3
Year of publication
1994
Pages
474 - 483
Database
ISI
SICI code
0895-4801(1994)7:3<474:ECID>2.0.ZU;2-T
Abstract
It is proved that every strongly connected directed graph with n nodes and at least [(n + 1)2/4] edges must contain an even cycle. This is b est possible, and the structure of extremal graphs is discussed.