PACKING DIRECTED CIRCUITS EXACTLY

被引：19

作者：

Guenin, Bertrand ^{[1
]}

Thomas, Robin ^{[2
]}

机构：

[1] Univ Waterloo, Fac Math, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

[2] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA

来源：

COMBINATORICA | 2011年 / 31卷 / 04期

关键词：

GRAPHS; THEOREM;

D O I：

10.1007/s00493-011-1687-5

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We give an "excluded minor" and a "structural" characterization of digraphs D that have the property that for every subdigraph H of D, the maximum number of disjoint circuits in H is equal to the minimum cardinality of a set T subset of V (H) such that H\T is acyclic.

引用

页码：397 / 421

页数：25

共 9 条

[1] A min-max theorem on feedback vertex sets [J].

Cai, MC ;

Deng, XT ;

Zang, WN .

MATHEMATICS OF OPERATIONS RESEARCH, 2002, 27 (02) :361-371

[2] Packing cycles in graphs [J].

Ding, GL ;

Zang, WN .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 86 (02) :381-407

[3] CHARACTERIZATION OF CONVERTIBLE (0,1)-MATRICES [J].

LITTLE, CHC .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1975, 18 (03) :187-208

[4] MINIMAX THEOREM FOR DIRECTED GRAPHS [J].

LUCCHESI, CL ;

YOUNGER, DH .

JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 1978, 17 (JUN) :369-374

[5]

McCuaig W., 2004, Electron. J. Combin, V11, P83, DOI DOI 10.37236/1832

[6] Packing directed circuits [J].

Reed, B ;

Robertson, N ;

Seymour, P ;

Thomas, R .

COMBINATORICA, 1996, 16 (04) :535-554

[7] Permanents, Pfaffian orientations, and even directed circuits [J].

Robertson, N ;

Seymour, PD ;

Thomas, R .

ANNALS OF MATHEMATICS, 1999, 150 (03) :929-975

[8] CHARACTERIZATION OF EVEN DIRECTED-GRAPHS [J].

SEYMOUR, P ;

THOMASSEN, C .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1987, 42 (01) :36-45

[9]

ZANG W, 1998, P 39 IEEE S FDN COMP

← 1 →