Directed Cycles with two Chords and Strong Spanning Directed                Subgraphs with few Arcs

Carsten Thomassen

doi:10.1006/jctb.1996.0003

Directed Cycles with two Chords and Strong Spanning Directed Subgraphs with few Arcs

Research output: Contribution to journal › Journal article › Research › peer-review

Abstract

We prove the conjecture of D. A. Marcus (1981) that every strongly 2-arc-connected directed graph has a directed cycle with at least two chords. As a consequence, every strongly 2-arc-connected directed graph with m arcs has a spanning strong directed subgraph with less than 2/3m arcs. The constant 2/3 is best possible.

Original language	English
Journal	Journal of Combinatorial Theory. Series B
Volume	66
Issue number	1
Pages (from-to)	24-33
ISSN	0095-8956
DOIs	https://doi.org/10.1006/jctb.1996.0003
Publication status	Published - 1996

Access to Document

10.1006/jctb.1996.0003

OpenUrl availability

Full text

Cite this

@article{9f8a716a880d4f6a847663c45e02f2ea,

title = "Directed Cycles with two Chords and Strong Spanning Directed Subgraphs with few Arcs",

abstract = "We prove the conjecture of D. A. Marcus (1981) that every strongly 2-arc-connected directed graph has a directed cycle with at least two chords. As a consequence, every strongly 2-arc-connected directed graph with m arcs has a spanning strong directed subgraph with less than 2/3m arcs. The constant 2/3 is best possible.",

author = "Carsten Thomassen",

year = "1996",

doi = "10.1006/jctb.1996.0003",

language = "English",

volume = "66",

pages = "24--33",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press",

number = "1",

}

TY - JOUR

T1 - Directed Cycles with two Chords and Strong Spanning Directed Subgraphs with few Arcs

AU - Thomassen, Carsten

PY - 1996

Y1 - 1996

N2 - We prove the conjecture of D. A. Marcus (1981) that every strongly 2-arc-connected directed graph has a directed cycle with at least two chords. As a consequence, every strongly 2-arc-connected directed graph with m arcs has a spanning strong directed subgraph with less than 2/3m arcs. The constant 2/3 is best possible.

AB - We prove the conjecture of D. A. Marcus (1981) that every strongly 2-arc-connected directed graph has a directed cycle with at least two chords. As a consequence, every strongly 2-arc-connected directed graph with m arcs has a spanning strong directed subgraph with less than 2/3m arcs. The constant 2/3 is best possible.

U2 - 10.1006/jctb.1996.0003

DO - 10.1006/jctb.1996.0003

M3 - Journal article

SN - 0095-8956

VL - 66

SP - 24

EP - 33

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -

Directed Cycles with two Chords and Strong Spanning Directed Subgraphs with few Arcs

Abstract

Access to Document

OpenUrl availability

Fingerprint

Cite this