Largest 2-regular subgraphs in 3-regular graphs

DOI10.1007/S00373-019-02021-6zbMATH Open1416.05150arXiv1903.08795OpenAlexW2925142624WikidataQ128028917 ScholiaQ128028917MaRDI QIDQ2000571FDOQ2000571

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

Publication date: 28 June 2019

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

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.

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

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

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)

Cites Work

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

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)