Regular saturated graphs and sum-free sets

DOI10.1016/J.DISC.2021.112659zbMATH Open1475.05095arXiv2103.08831OpenAlexW3201704520MaRDI QIDQ2237233FDOQ2237233

Authors: Craig Timmons 

Publication date: 27 October 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: In a recent paper, Gerbner, Patk'{o}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 $K_3$-saturated graph with $n$ vertices. We extend this result to both $K_4$ and $K_5$ and prove some partial results for larger complete graphs. Using a variation of sum-free sets from additive combinatorics, we prove that for all $kgeq2$, there is a regular $C_{2k+1}$-saturated with $n$ vertices for infinitely many $n$. Studying the sum-free sets that give rise to $C_{2k+1}$-saturated graphs is an interesting problem on its own and we state an open problem in this direction.

Full work available at URL: https://arxiv.org/abs/2103.08831

Recommendations

• scientific article; zbMATH DE number 7633016
• Saturation problems with regularity constraints
• Few \(H\) copies in \(F\)-saturated graphs
• Onk-saturated graphs with restrictions on the degrees
• Cycle-saturated graphs of minimum size

zbMATH Keywords

extremal graph theorygraph saturationsum-free sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Additive bases, including sumsets (11B13)

Cites Work

• Saturated graphs with minimal number of edges
• A survey of minimum saturated graphs
• A Problem in Graph Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Additive Combinatorics
• A new critical pair theorem applied to sum-free sets in Abelian groups
• Minimalk-saturated and color critical graphs of prescribed minimum degree
• Maximal triangle‐free graphs with restrictions on the degrees
• Title not available (Why is that?)
• ON THE MAXIMUM SIZE OF A (k,l)-SUM-FREE SUBSET OF AN ABELIAN GROUP
• Sum-free sets in groups: a survey
• Onk-saturated graphs with restrictions on the degrees
• Saturated graphs of prescribed minimum degree
• The maximum size of \((k,l)\)-sum-free sets in cyclic groups

Cited In (2)

• Title not available (Why is that?)
• Saturation problems with regularity constraints

Uses Software

• Mathematica

This page was built for publication: Regular saturated graphs and sum-free sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2237233)