Packing directed circuits exactly

DOI10.1007/S00493-011-1687-5zbMATH Open1299.05144arXiv1012.2749OpenAlexW1964031838MaRDI QIDQ663091FDOQ663091

Authors: Robin Thomas, Bertrand Guenin 

Publication date: 13 February 2012

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (20)

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