Odd disjoint trails and totally odd graph immersions

Odd disjoint trails and totally odd graph immersions

PhD thesis at Simon Fraser University

I have succesfully defended my PhD thesis! It's "packed" with results on graph immersions with parity restrictions, and "covers" odd edge-connectivity, totally odd clique immersions, and a new submodular measure that's intimately connected with both.

The odd edge-connectivity between two vertices in a graph is the maximum number λo(u,v)\lambda_o(u, v) of edge-disjoint (u,v)(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)\lambda_o(u, v) is bounded above and below by constant factors of the usual edge-connectivity λ(u,v)\lambda(u, v) and/or the minimum perimeter among vertex-sets containing uu and vv.

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)\lambda_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 HH in another graph GG is a representation in which vertices in HH correspond to vertices in GG and edges in HH correspond to edge-disjoint odd trails in GG. 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 KtK_t. Finally, we suggest a totally odd immersion variant of Hadwiger’s Conjecture and show that it is true for almost all graphs.

Ross Churchley [1]

Slides from my defence can be found here. I am grateful to NSERC for funding my degree with a Alexander Graham Bell Canada Graduate Scholarship, and to my supervisor Bojan Mohar.

  1. Odd disjoint trails and totally odd graph immersions. Ross Churchley (2017). ↩︎