Large 2-regular Subgraphs in Subcubic Graphs

Boram Park, Ajou University
A312 Academic Building

For a graph GG, let f2(G) denote the largest number of vertices in a 2-regular subgraph of GG. We determine the minimum of f2(G)f2G over 3-regular nn-vertex simple graphs G. To do this, we prove that every 3-regular multigraph with exactly cc cut-edges has a 2-regular subgraph that omits at most max{0,⌊(c - 1) / 2⌋}max⁡{0,c-12} vertices. More generally, every nn-vertex multigraph with maximum degree 3 and mm edges has a 2-regular subgraph that omits at most max{0,⌊(3n - 2m + c - 1) / 2⌋}max⁡{0,3n-2m+c-12}  vertices. These bounds are sharp; we describe the extremal multigraphs.

The work is based on joint work with Ilkyoo Choi, Ringi Kim, Alexandr Kostochka, and Douglas B. West.