Regular saturated graphs and sum-free sets |
| |
Affiliation: | Department of Mathematics and Statistics, California State University Sacramento, 6000 J Street, Sacramento, CA 95819, USA |
| |
Abstract: | In a recent paper, Gerbner, Patkós, Tuza and Vizer studied regular F-saturated graphs. One of the essential questions is given F, for which n does a regular n-vertex F-saturated graph exist. They proved that for all sufficiently large n, there is a regular -saturated graph with n vertices. We extend this result to both and and prove some partial results for larger complete graphs. Using a variation of sum-free sets from additive combinatorics, we prove that for all , there is a regular -saturated with n vertices for infinitely many n. Studying the sum-free sets that give rise to -saturated graphs is an interesting problem on its own and we state an open problem in this direction. |
| |
Keywords: | Graph saturation Sum-free sets Extremal graph theory |
本文献已被 ScienceDirect 等数据库收录! |
|