Spannning a strong digraph by circuits: a proof of Gallai's conjecture

DOI10.1007/S00493-007-2073-3MaRDI QIDQ949757zbMATH OpenOpenAlexWikidataFDO

Authors Stéphane Bessy, Stéphan Thomassé

Publication date 21 October 2008

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-007-2073-3

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38)

Recommendations

• Integer Programming and Combinatorial Optimization
• Every strong digraph has a spanning strong subgraph with at most \(n+2\alpha-2\) arcs
• Covering a strong digraph by \(\alpha-1\) disjoint paths: A proof of Las Vergnas' conjecture
• The Gallai-Younger conjecture for planar graphs
• Paths and stability number in digraphs

Cites work

• scientific article; zbMATH DE number 3150485 (Why is no real title available?)
• scientific article; zbMATH DE number 3165195 (Why is no real title available?)
• scientific article; zbMATH DE number 863469 (Why is no real title available?)
• scientific article; zbMATH DE number 3258857 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• A short proof of the Chen-Manalastas theorem
• Circular chromatic number: A survey
• Diconnected Orientations and a Conjecture of Las Vergnas
• Every finite strongly connected digraph of stability 2 has a Hamiltonian path
• Path Partitions in Directed Graphs

Cited in

(13)

• Variations on the Gallai-Milgram theorem
• Path Partitions, Cycle Covers and Integer Decomposition
• A short proof of the Chen-Manalastas theorem
• BE-diperfect digraphs with stability number two
• A network flow approach to a common generalization of Clar and Fries numbers
• Every strong digraph has a spanning strong subgraph with at most \(n+2\alpha-2\) arcs
• Berge's conjecture on directed path partitions -- a survey
• Structural properties of minimal strong digraphs versus trees
• Cyclic orders: equivalence and duality
• Integer Programming and Combinatorial Optimization
• Covering a strong digraph by \(\alpha-1\) disjoint paths: A proof of Las Vergnas' conjecture
• Shortcutting directed and undirected networks with a degree constraint
• Structural and spectral properties of minimal strong digraphs

This page was built for publication: Spannning a strong digraph by \(\alpha\) circuits: a proof of Gallai's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q949757)