首页 | 本学科首页   官方微博 | 高级检索  
     


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 K3-saturated graph with n vertices. We extend this result to both K4 and K5 and prove some partial results for larger complete graphs. Using a variation of sum-free sets from additive combinatorics, we prove that for all k2, there is a regular C2k+1-saturated with n vertices for infinitely many n. Studying the sum-free sets that give rise to C2k+1-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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号