Faculty of Mathematics, Physics
and Informatics
Comenius University in Bratislava

Seminar of Graph Theory - Anna Kompišová (24.10.2019)

Thursday 24.10.2019 at 9:50, Lecture room M/213

22. 10. 2019 10.23 hod.
By: Martin Škoviera

Anna Kompišová:
Short cycle covers of graphs with minimum degree 3 with loops

Let $G$ be a bridgeless graph and let $cc(G)$ denote the length of a shortest cycle cover of $G$. The best known result for the general case, $cc(G) \leq {5 \over 3}|E(G)|$ $(\approx 1.6667|E(G)|)$, was established over 35 years ago. Recently, Fan proved that $cc(G) < 1.6258|E(G)|$ for graphs with minimum degree at least 3 (loops being allowed) and $cc(G) < 1.6148|E(G)|$ for loopless graphs with minimum degree at least 3. We improve his first result by proving that $cc(G) < 1.0741|S| + 1.6148|E(G)-S|$ where $S$ denotes the set of loops of a graph $G$. This implies that if $G$ has minimum degree at least 3, then $cc(G) < 1.6148|E(G)|$.

This is a joint work with Robert Lukoťka.