Premium
Packing odd T ‐joins with at most two terminals
Author(s) -
Abdi Ahmad,
Guenin Bertrand
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22178
Subject(s) - combinatorics , joins , mathematics , bipartite graph , cardinality (data modeling) , conjecture , eulerian path , disjoint sets , graph , set (abstract data type) , discrete mathematics , computer science , programming language , lagrangian , mathematical physics , data mining
Take a graph G , an edge subset Σ ⊆ E ( G ) , and a set of terminals T ⊆ V ( G ) where | T | is even. The triple ( G , Σ , T ) is called a signed graft . A T ‐join is odd if it contains an odd number of edges from Σ. Let ν be the maximum number of edge‐disjoint odd T ‐joins. A signature is a set of the form Σ ▵ δ ( U ) where U ⊆ V ( G ) and | U ∩ T | is even. Let τ be the minimum cardinality a T ‐cut or a signature can achieve. Then ν ≤ τ and we say that ( G , Σ , T )packs if equality holds here. We prove that ( G , Σ , T ) packs if the signed graft is Eulerian and it excludes two special nonpacking minors. Our result confirms the Cycling Conjecture for the class of clutters of odd T ‐joins with at most two terminals. Corollaries of this result include, the characterizations of weakly and evenly bipartite graphs, packing two‐commodity paths, packing T ‐joins with at most four terminals, and a new result on covering edges with cuts.