Longest paths in 2-edge-connected cubic graphs

Published
Oded Lachish
Felix Reidl
Nikola K. Blanchard
Eldar Fischer
Abstract: We prove almost tight bounds on the length of paths in $2$-edge-connected cubic graphs. Concretely, we show that (i) every $2$-edge-connected cubic graph of size $n$ has a path of length $\Omega(\log_2 n / \log\log n)$, and (ii) there exists a $2$-edge-connected cubic graph, such that every path in the graph has length $O(\log_2 n)$.

Felix Reidl

Felix is a Senior Lecturer at Birkbeck. His speciality is the design of algorithms for sparse graphs.

Oded Lachish

Oded is a Reader at Birkbeck. His speciality are analysis of algorithms, in particular using the probabilistic method.