A digraph G is called strongly connected if its underlying undirected graph is connected and each arc of G is contained in a cycle. By an ear decomposition of G we mean a sequence of strongly connected digraphs G_0, ..., G_n where G_0 is a graph consisting of a single node, G_n = G, and G_{i+1} is obtained from G_i by adding a path (called ear) whose endpoints belong to the nodeset of $G_i$ and all other nodes do not belong that set. One can easily show that each strongly connected digraph admits an ear decomposition.
During the talk we will explain how these ideas can be extended to the case of bidirected graphs. It will turn out that unlike the standard directed case on certain steps one may need to add a pair of ears rather than a single ear.
In particular, our results imply a well-known theorem (which is due to Lovasz and Plummer) on two ear decompositions of matching coverable graphs.
© 2006—2007 Kolmogorov seminar
Feedback