DIRECTED CYCLES WITH 2 CHORDS AND STRONG SPANNING DIRECTED SUBGRAPHS WITH FEW ARCS

Authors
THOMASSEN C
Citation
C. Thomassen, DIRECTED CYCLES WITH 2 CHORDS AND STRONG SPANNING DIRECTED SUBGRAPHS WITH FEW ARCS, J COMB TH B, 66(1), 1996, pp. 24-33
Citations number
3
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956 → ACNP
Volume
66
Issue
1
Year of publication
1996
Pages
24 - 33
Database
ISI
SICI code
0095-8956(1996)66:1<24:DCW2CA>2.0.ZU;2-L
Abstract
We prove the conjecture of D. A. Marcus (1981) that every strongly 2-a rc-connected directed graph has a directed cycle with at least two cho rds. As a consequence, every strongly 2-arc-connected directed graph w ith m arcs has a spanning strong directed subgraph with less than 2/3m arcs. The constant 2/3 is best possible. (C) 1996 Academic Press, Inc .