Seminár z teórie grafov - Anna Kompišová (24.10.2019)

vo štvrtok 24.10.2019 o 9:50 hod. v miestnosti M/213

---

Prednášajúci: Anna Kompišová

Názov: Short cycle covers of graphs with minimum degree 3 with loops

Termín: 24.10.2019, 9:50 hod., M/213

Abstrakt:
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.

---