Abstract
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 ⊆ V(H) such that H\T is acyclic.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
W. McCuaig: Pólya’s permanent problem, Electron. J. Combin. 11 (2004), 83.
G. Ding and W. Zang: Packing cycles in graphs, J. Combin. Theory Ser. B 86 (2002), 381–407.
C. H. C. Little: A characterization of convertible (0, 1)-matrices, J. Combin. Theory Ser. B 18 (1975), 187–208.
C. L. Lucchesi and D. H. Younger: A minimax relation for directed graphs, J. London Math. Soc. 17 (1978), 369–374.
B. Reed, N. Robertson, P. D. Seymour and R. Thomas: Packing directed circuits, Combinatorica 16 (1996), 535–554.
N. Robertson, P. D. Seymour and R. Thomas: Permanents, Pfaffian orientations, and even directed circuits, Ann. Math. 150 (1999), 929–975.
P. D. Seymour and C. Thomassen: Characterization of even directed graphs, J. Combin. Theory Ser. B 42 (1987), 36–45.
W. Zang, M. Cai and X. Deng: A TDI system and its application to approximation algorithm, Proc. 39th IEEE Symposium on Foundations of Computer Science, (1998).
W. Zang, M. Cai and X. Deng: A min-max theorem on feedback vertex sets, Math. of Operations research, 27, (2002), 361–371.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research partially supported by NSF under Grant No. DMS 96-32032 and Grant No. DMS-9970514.