Largest 2-regular subgraphs in 3-regular graphs

DOI10.1007/S00373-019-02021-6MaRDI QIDQ2000571zbMATH OpenOpenAlexWikidataFDO

Authors Ilkyoo Choi, Ringi Kim, Boram Park, Douglas B. West, Alexandr Kostochka

Publication date 28 June 2019

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.08795

zbMATH Keywords

cubic graphsfactors in graphscut-edges

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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 $max0,lfloor(c-1)/2floor$ vertices. More generally, every $n$-vertex multigraph with maximum degree $3$ and $m$ edges has a $2$-regular subgraph that omits at most $max0,lfloor(3n-2m+c-1)/2floor$ vertices. These bounds are sharp; we describe the extremal multigraphs.

Recommendations

• Dense graphs without 3-regular subgraphs
• Cut-edges and regular factors in regular graphs of odd degree
• Induced cycles in graphs
• Three-regular subgraphs of four-regular graphs
• Note on regular subgraphs

Cites work

• scientific article; zbMATH DE number 3211575 (Why is no real title available?)
• scientific article; zbMATH DE number 3390835 (Why is no real title available?)
• Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree
• Cut-edges and regular factors in regular graphs of odd degree
• Dynamic cage survey
• Matchings in regular graphs
• Maximum matching and a polyhedron with 0,1-vertices
• On interval colourings of bi-regular bipartite graphs
• Paths, Trees, and Flowers
• Sharp bounds for the Chinese postman problem in 3-regular graphs and multigraphs
• The Factorization of Linear Graphs
• Tight lower bounds on the size of a maximum matching in a regular graph

This page was built for publication: Largest 2-regular subgraphs in 3-regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2000571)