Name
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
$$\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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s00373-019-02021-6 | Graphs and Combinatorics |
Keywords | Field | DocType |
Factors in graphs, Cubic graphs, Cut-edges, 05C07, 05C70, 05C35 | Graph,Combinatorics,Multigraph,Vertex (geometry),Cubic graph,Degree (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
35 | 4 | 0911-0119 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ilkyoo Choi | 1 | 26 | 12.04 |
| ringi kim | 2 | 7 | 2.96 |
| Alexandr V. Kostochka | 3 | 682 | 89.87 |
| boram park | 4 | 5 | 5.89 |
| Douglas B. West | 5 | 1176 | 185.69 |