Longest paths in 2-edge-connected cubic graphs
classification
💻 cs.DM
math.CO
keywords
cubicedge-connectedgraphlengtheverygraphspathpaths
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.