Spannning a strong digraph by \(\alpha\) circuits: a proof of Gallai's conjecture

DOI10.1007/s00493-007-2073-3zbMath1236.05091OpenAlexW1981468140WikidataQ123151409 ScholiaQ123151409MaRDI QIDQ949757

Steéphan Thomassé, Stéphane Bessy

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

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

Related Items (6)

Structural properties of minimal strong digraphs versus trees ⋮ Berge's conjecture on directed path partitions -- a survey ⋮ Shortcutting directed and undirected networks with a degree constraint ⋮ Cyclic orders: equivalence and duality ⋮ Structural and spectral properties of minimal strong digraphs ⋮ Path Partitions, Cycle Covers and Integer Decomposition

Cites Work

• Every finite strongly connected digraph of stability 2 has a Hamiltonian path
• A short proof of the Chen-Manalastas theorem
• A decomposition theorem for partially ordered sets
• Path Partitions in Directed Graphs
• Diconnected Orientations and a Conjecture of Las Vergnas
• Circular chromatic number: A survey
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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