Odd disjoint trails and totally odd graph immersions

The odd edge-connectivity between two vertices in a graph is the maximum number λ_o(u,v) of edge-disjoint (u, v)-trails of odd length. In this thesis, we define the perimeter of a vertex- set, a natural upper bound for the odd edge-connectivity between some of its constituent pairs. Our central result is an approximate characterization of odd edge-connectivity: λ_o(u, v) is bounded above and below by constant factors of the usual edge-connectivity λ_o(u, v) and/or the minimum perimeter among vertex-sets containing u and v. The relationship between odd edge-connectivity and perimeter has many implications, most notably a loose packing–covering duality for odd trails. (In contrast, odd paths do not obey any such duality.) For Eulerian graphs, we obtain a second, independent proof of the packing–covering duality with a significantly better constant factor. Both proofs can be implemented as polynomial-time approximation algorithms for λ_o(u,v). After observing that perimeter satisfies a submodular inequality, we are able to prove an analogue of the Gomory–Hu Theorem for sets of minimum perimeter and, consequently, to construct an efficient data structure for storing approximate odd edge-connectivities for all vertex pairs in a graph. The last part of the thesis studies more complicated systems of odd trails. A totally odd immersion of a graph H in another graph G is a representation in which vertices in H correspond to vertices in G and edges in H correspond to edge-disjoint odd trails in G. Using our perimeter version of the Gomory–Hu Theorem, we describe the rough structure of graphs with no totally odd immersion of the complete graph K_t. Finally, we suggest a totally odd immersion variant of Hadwiger’s Conjecture and show that it is true for almost all graphs.