A lower bound on the saturation number, and graphs for which it is sharp

DOI10.1016/J.DISC.2022.112867MaRDI QIDQ2138956zbMATH OpenOpenAlexFDO

Authors Alex Cameron, Gregory J. Puleo

Publication date 17 May 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

dominating vertexsaturationthreshold graphweight function

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: Let $H$ be a fixed graph. We say that a graph $G$ is $H$-saturated if it has no subgraph isomorphic to $H$, but the addition of any edge to $G$ results in an $H$-subgraph. The saturation number $mathrmsat(H,n)$ is the minimum number of edges in an $H$-saturated graph on $n$ vertices. K'aszonyi and Tuza, in 1986, gave a general upper bound on the saturation number of a graph $H$, but a nontrivial lower bound has remained elusive. In this paper we give a general lower bound on $mathrmsat(H,n)$ and prove that it is asymptotically sharp (up to an additive constant) on a large class of graphs. This class includes all threshold graphs and many graphs for which the saturation number was previously determined exactly. Our work thus gives an asymptotic common generalization of several earlier results. The class also includes disjoint unions of cliques, allowing us to address an open problem of Faudree, Ferrara, Gould, and Jacobson.

Recommendations

• Results and problems on saturation numbers for linear forests
• scientific article; zbMATH DE number 6686834
• Saturation numbers for disjoint stars
• tK\(_p\)-saturated graphs of minimum size
• Saturation numbers for nearly complete graphs

Cites work

• A Problem in Graph Theory
• A survey of minimum saturated graphs
• scientific article; zbMATH DE number 4081590 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• Saturated graphs with minimal number of edges
• Saturation numbers for nearly complete graphs
• Saturation numbers for trees
• Saturation numbers of books
• Threshold graphs and related topics
• tK\(_p\)-saturated graphs of minimum size

Cited in

(18)

• tK\(_p\)-saturated graphs of minimum size
• Saturation problems in the Ramsey theory of graphs, posets and point sets
• Saturation numbers for disjoint stars
• Graph cover-saturation
• Saturation numbers for nearly complete graphs
• A note on the saturation number of the family of \(k\)-connected graphs
• Oriented graph saturation
• Sharp bounds on the order, size, and stability number of graphs
• Some results on the saturation number for unions of cliques
• Saturation numbers of joins of graphs
• Some results on minimum saturated graphs
• The saturation number of wheels
• A lower bound on the saturation number and a strengthening for triangle-free graphs
• Some results on the saturation number of graphs
• Saturation numbers of bipartite graphs in random graphs
• (K₁ P_t)-saturated graphs with minimum number of edges
• The saturation number of W₄
• Saturation numbers of K₂ P_k

This page was built for publication: A lower bound on the saturation number, and graphs for which it is sharp

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