Vertex connectivity of Eulerian orientations

Pranshu Gaba
Ashutosh Shankar
Friday, 9 Jul 2021, 15:00 to 16:00
A directed graph is said to be k-vertex-connected if after deleting any k-1 vertices, therer is a directed path from every vertex to every other vertex along the directed edges. An Eulerian orientation of a graph is an orientation such that every vertex has equal indegree and outdegree. Given an 2k-regular graph G, we would like to know if every Eulerian orientation of G is k-vertex connected. Horsch and Szigeti showed that this property holds for complete bipartite graphs, line graphs of regular complete bipartite graphs, incidence graphs of projective planes, but not for most complete graphs. In this talk, we will go through their proofs. We will also show that this property does not hold for most regular complete multipartite graphs. Link to paper: Zoom link is: