Packing directed circuits exactly

DOI10.1007/S00493-011-1687-5MaRDI QIDQ663091zbMATH OpenOpenAlexFDO

Authors Robin Thomas, Bertrand Guenin

Publication date 13 February 2012

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.2749

zbMATH Keywords

minorsstrongly connected digraphsmaximum packing of circuitsminimum transversalsstrongly planar digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Minimax problems in mathematical programming (90C47)

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 subset T of V(H) such that HT is acyclic.

Recommendations

• Packing directed circuits
• Packing directed circuits fractionally
• Packing directed circuits quarter-integrally
• Packing directed circuits through prescribed vertices bounded fractionally
• Packing directed cycles efficiently
• Mathematical Foundations of Computer Science 2004
• Packing circuits into \(K_N\).
• Packings of the complete directed graph with \(m\)-circuits
• Labeled packing of cycles and circuits
• Packing circuits in eulerian digraphs

Cites work

• A Min-Max Theorem on Feedback Vertex Sets
• A Minimax Theorem for Directed Graphs
• Characterization of even directed graphs
• Packing cycles in graphs
• Packing directed circuits
• Permanents, Pfaffian orientations, and even directed circuits
• Pólya's permanent problem

Cited in

(20)

• Ranking tournaments with no errors. I: Structural description
• Optimal packing of even circuits into a \(\text{DK}_ v\)
• Colouring non-even digraphs
• Number of fixed points and disjoint cycles in monotone Boolean networks
• Digraphs of directed treewidth one
• On the number of vertex-disjoint cycles in digraphs
• scientific article; zbMATH DE number 1762085 (Why is no real title available?)
• Packing circuits in eulerian digraphs
• Packing circuits into \(K_N\).
• Excluding a planar matching minor in bipartite graphs
• Ranking tournaments with no errors. II: Minimax relation
• Even circuits in oriented matroids
• Recent techniques and results on the Erdős-Pósa property
• Packing cycles in graphs. II
• Packing Odd Circuits
• Erdős–Pósa property of obstructions to interval graphs
• Packing directed cycles efficiently
• Erdös-Pósa Property of Obstructions to Interval Graphs
• Some novel minimax results for perfect matchings of hexagonal systems
• Euler digraphs

This page was built for publication: Packing directed circuits exactly

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