pith. sign in

arxiv: 1903.02508 · v1 · pith:H3YBA6Y4new · submitted 2019-03-06 · 💻 cs.DM · math.CO

Longest paths in 2-edge-connected cubic graphs

classification 💻 cs.DM math.CO
keywords cubicedge-connectedgraphlengtheverygraphspathpaths
0
0 comments X
read the original 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\left(\frac{\log^2{n}}{\log{\log{n}}}\right)$, and (ii) there exists a $2$-edge-connected cubic graph, such that every path in the graph has length $O(\log^2{n})$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.