Largest 2-regular subgraphs in 3-regular graphs

التفاصيل البيبلوغرافية
العنوان: Largest 2-regular subgraphs in 3-regular graphs
المؤلفون: Choi, Ilkyoo, Kim, Ringi, Kostochka, Alexandr, Park, Boram, West, Douglas B.
سنة النشر: 2019
المجموعة: Mathematics
مصطلحات موضوعية: Mathematics - Combinatorics
الوصف: 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,\lfloor (c-1)/2\rfloor\}$ 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,\lfloor (3n-2m+c-1)/2\rfloor\}$ vertices. These bounds are sharp; we describe the extremal multigraphs.
نوع الوثيقة: Working Paper
URL الوصول: http://arxiv.org/abs/1903.08795
رقم الأكسشن: edsarx.1903.08795
قاعدة البيانات: arXiv