Common Cyclic Structure

The following is a summary of Circuits through prescribed edges [KP2020] which is joint work with Max Pitz. In 2020 it is published in Journal of Graph Theory. You can find a preprint on arXiv. This paper is an extract from my Bachelor's thesis, which I created under the supervision of Max.

Main result

1.) Given a connected graph G and a natural number k, every set of k edges lies on a common circuit if and only if G has no odd cut of size at most k [KP2020, Theorem 1.4].

2.) Every k edges in a graph whose edge-connectivity is at least 2·⌈(k+1)/2⌉ lie on a common circuit [KP2020, Lemma 5.3].

Summary

A rather simple question to ask is: when do k prescribed edges of a graph lie on a common cycle? Lovasz [Lov73] and independently also Woodall [Woo77] conjectured that 

Every k pairwise independent edges on a k-connected graph lie on a common cycle, if k is even or if after its deletion the graph is still connected. 

Building on Woodall's 'Hopping Lemma' technique, Häggkvist & Thomassen [HT82] and Kawarabayashi [Kaw02] showed two weakenings of the Lovasz-Woodall-Conjecture: Häggkvist & Thomasssn set out from the stronger assumption of (k+1)- instead of k-connectedness, and Kawarabayashi obtained a weaker conclusion, namely, at most two vertex-disjoint cycles instaead of one.

A relaxation of the concept of cycles are circuits: Formally, a cycle may be described as a cyclic sequence alternating between vertices and edges such that the predecessor and the successor of every edge are both its endvertices and in which no vertex appears twice. A circuit is a cyclic sequence such as cycles  in which vertices now may appear multiple times but no edge appears twice. 

In light of the above mentioned Lovasz-Woodall-Conjecture, it is natural to ask: When do k prescribed edges in a graph lie on a common circuit? We answer this question by giving a sufficient global condition: the underlying graph is connected and has no odd cut of size at most k; in particular, every graph with edge-connectivity at least 2·⌈(k+1)/2⌉ satisfies this condition. Our proof heavily relies on an adaption of Woodall's Hopping Lemma technique to edge-connectivity.

References

[HT82] R. Häggkvist and C. Thomassen, Circuits through specified edges, Discrete Mathematics 41.1 (1982): 29–34.

[Kaw02] K.-I. Kawarabayashi, One or two disjoint circuits cover independent edges: Lovász-Woodall Conjecture, Journal of Combinatorial Theory, Series B 84.1 (2002): 1–44.

[Lov73] L. Lovász, Problem 5, Periodica Mathematica Hungarica 4 (1973): 82.

[Woo77] D. R. Woodall, Circuits containing specified edges, Journal of Combinatorial Theory, Series B 22.3 (1977): 274–278.