Regular saturated graphs and sum-free sets

DOI10.1016/J.DISC.2021.112659MaRDI QIDQ2237233zbMATH OpenOpenAlexFDO

Authors Craig Timmons

Publication date 27 October 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

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)

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.

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

Cites work

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

Cited in

(2)

• scientific article; zbMATH DE number 7633016 (Why is no real title available?)
• Saturation problems with regularity constraints

Describes a project that uses

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)