Generalized sum-free sets and cycle saturated regular graphs

Abstract

Gerbner, Patkós, Tuza, and Vizer recently initiated the study of $F$-saturated regular graphs. One of the essential problems in this line of research is determining when such a graph exists. Using generalized sum-free sets we prove that for any odd integer $k\ge 5$, there is an $n$-vertex regular $C_k$-saturated graph for all $n\ge n_k$. Our proof is based on constructing a special type of sum-free set in ${\mathbb{Z}}_n$. We prove that for all even $\ell \ge 4$ and integers $n>12{\ell }^2+36\ell +24$, there is a symmetric complete $(\ell ,1)$-sum-free set in ${\mathbb{Z}}_n$. We pose the problem of finding the minimum size of such a set, and present some examples found by a computer search.

References in corpus (1)

• Some exact results for regular Turán problems