pith. sign in

arxiv: 1901.10718 · v1 · pith:JOELPJYKnew · submitted 2019-01-30 · 🧮 math.CO · cs.DM

Short cycle covers of cubic graphs and intersecting 5-circuits

classification 🧮 math.CO cs.DM
keywords covercyclegraphlengthapproxcdotcubiccycles
0
0 comments X
read the original abstract

A cycle cover of a graph is a collection of cycles such that each edge of the graph is contained in at least one of the cycles. The length of a cycle cover is the sum of all cycle lengths in the cover. We prove that every bridgeless cubic graph with $m$ edges has a cycle cover of length at most $212/135 \cdot m \ (\approx 1.570 m)$. Moreover, if the graph is cyclically $4$-edge-connected we obtain a cover of length at most $47/30 \cdot m \approx 1.567 m$.

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.