Largest 2-regular subgraphs in 3-regular graphs

Ilkyoo Choi (최일규)
Department of Mathematics, Hankuk University of Foreign Studies, Yongin-si

2018/11/26 Mon 5PM-6PM (Bldg. E6-1, Room 1401)

For a graph G, let f_{2}(G) denote the largest number of vertices in a 2-regular subgraph of G. We determine the minimum of f_{2}(G) over 3-regular n-vertex simple graphs G.

To do this, we prove that every 3-regular multigraph with exactly c cut-edges has a 2-regular subgraph that omits at most max{0,⎣(c-1)/2⎦} vertices.

More generally, every n-vertex multigraph with maximum degree 3 and m edges has a 2-regular subgraph that omits at most max{0, ⎣(3n-2m+c-1)/2⎦} vertices.

These bounds are sharp; we describe the extremal multigraphs.

This is joint work with Ringi Kim, Alexandr V. Kostochka, Boram Park, and Douglas B. West.