On the infinite Lucchesi–Younger conjecture I

DOI10.1002/JGT.22680MaRDI QIDQ6056771zbMATH OpenOpenAlexWikidataFDO

Authors J. Pascal Gollin, Karl Heuer

Publication date 4 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

(finitary) dijoindirected cutsinfinite digraphsinfinite Lucchesi-Younger conjectureoptimal pair

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Infinite graphs (05C63) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A dicut in a directed graph is a cut for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of an edge set meeting every dicut equals the maximum number of disjoint dicuts in that digraph. In this first paper out of a series of two papers, we conjecture a version of this theorem using a more structural description of this min-max property for finite dicuts in infinite digraphs. We show that this conjecture can be reduced to countable digraphs where the underlying undirected graph is $2$-connected, and we prove several special cases of the conjecture.

Recommendations

• Disjoint dijoins for classes of dicuts in finite and infinite digraphs
• On dijoins
• Disjoint dijoins
• On partitioning the edges of an infinite digraph into directed cycles
• Packing directed circuits

Cites work

• A Minimax Theorem for Directed Graphs
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• Connections in combinatorial optimization
• Digraphs
• Infinite matching theory
• Menger's theorem for infinite graphs
• Minimization of Some Nonlinear Functions over Polymatroidal Network Flows
• On two minimax theorems in graph

Cited in

(1)

• Disjoint dijoins for classes of dicuts in finite and infinite digraphs

This page was built for publication: On the infinite Lucchesi–Younger conjecture I

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