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 results

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\cdot\lceil (k+1)/2 \rceil$ 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? Lovász [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 Lovász-Woodall-Conjecture: Häggkvist & Thomassen 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 instead 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 Lovász-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\cdot\lceil (k+1)/2 \rceil$ 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.