Name
Abstract | ||
|---|---|---|
For a graph F, we say that another graph G is F-saturated, if G is F-free and adding any edge to G would create a copy of F. We study for a given graph F and integer n whether there exists a regular n-vertex F-saturated graph, and if it does, what is the smallest number of edges of such a graph. We mainly focus on the case when F is a complete graph and prove for example that there exists a K-3-saturated regular graph on n vertices for every large enough n. We also study two relaxed versions of the problem: when we only require that no regular F-free supergraph of G should exist or when we drop the F-free condition and only require that any newly added edge should create a new copy of F. (c) 2022 The Author(s). Published by Elsevier B.V. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.disc.2022.112921 | DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
Saturation problems, Regular graphs | Journal | 345 |
Issue | ISSN | Citations |
8 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dániel Gerbner | 1 | 46 | 21.61 |
| Balázs Patkós | 2 | 85 | 21.60 |
| Zsolt Tuza | 3 | 1889 | 262.52 |
| Máté Vizer | 4 | 27 | 14.06 |