











Title 


Date 
20181126 


Host 



Place 
KAIST 




Abstract : For a graph G, let f2(G) denote the largest number of vertices in a 2regular subgraph of G. We determine the minimum of f2(G) over 3regular nvertex simple graphs G. To do this, we prove that every 3regular multigraph with exactly c cutedges has a 2regular subgraph that omits at most max{0,⎣(c1)/2⎦} vertices.
More generally, every nvertex multigraph with maximum degree 3 and m edges has a 2regular subgraph that omits at most max{0, ⎣(3n2m+c1)/2⎦} vertices. More generally, every nvertex multigraph with maximum degree 3 and m edges has a 2regular subgraph that omits at most max{0, ⎣(3n2m+c1)/2⎦} vertices.






