Saturated graphs of prescribed minimum degree

DOI10.1017/S0963548316000377MaRDI QIDQ5366942zbMATH OpenOpenAlexFDO

Authors A. Nicholas Day

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

graphs construction

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35)

Abstract: A graph $G$ is $H$-saturated if it contains no copy of $H$ as a subgraph but the addition of any new edge to $G$ creates a copy of $H$. In this paper we are interested in the function sat${}_t(n,p)$, defined to be the minimum number of edges that a $K_p$-saturated graph on $n$ vertices can have if it has minimum degree at least $t$. We prove that sat${}_t(n,p)=tn-O(1)$, where the limit is taken as $n$ tends to infinity. This confirms a conjecture of Bollob'as when $p=3$. We also present constructions for graphs that give new upper bounds for sat${}_t(n,p)$ and discuss an analogous problem for saturated hypergraphs.

Recommendations

• Minimum degree and the minimum size of \(K_2^t\)-saturated graphs
• tK\(_p\)-saturated graphs of minimum size
• Minimum \(t P_3\)-saturation graphs
• Onk-saturated graphs with restrictions on the degrees
• MinimumK_{2, 3}-Saturated Graphs

Cites work

• A Problem in Graph Theory
• A short proof of Sperner's lemma
• A survey of minimum saturated graphs
• A Theorem on k-Saturated Graphs
• Generalization of Sperner’s Theorem on the Number of Subsets of a Finite Set
• scientific article; zbMATH DE number 830463 (Why is no real title available?)
• scientific article; zbMATH DE number 2192110 (Why is no real title available?)
• Logarithmic order of free distributive lattice
• Maximal triangle‐free graphs with restrictions on the degrees
• Minimalk-saturated and color critical graphs of prescribed minimum degree
• On generalized graphs
• On maximal triangle‐free graphs
• Onk-saturated graphs with restrictions on the degrees

Cited in

(19)

• tK\(_p\)-saturated graphs of minimum size
• Saturation numbers for Ramsey-minimal graphs
• Cycle-saturated graphs of minimum size
• Minimum \(t P_3\)-saturation graphs
• On the size of \((K_t, K_{1, k})\)-co-critical graphs
• On the size of \((K_t, P_k)\)-co-critical graphs
• On the size of \((K_t,\mathcal{T}_k)\)-co-critical graphs
• Regular saturated graphs and sum-free sets
• The minimum number of clique-saturating edges
• Saturated Simple and 2-simple Topological Graphs with Few Edges
• Oriented graph saturation
• scientific article; zbMATH DE number 3865320 (Why is no real title available?)
• Onk-saturated graphs with restrictions on the degrees
• Min-max and max-min graph saturation parameters
• Triangles in K_s-saturated graphs with minimum degree t
• \(K_r\)-saturated graphs and the two families theorem
• Minimizing the number of complete bipartite graphs in a K_s-saturated graph
• On saturation problems for matchings with regularity constraints
• Minimum degree and the minimum size of \(K_2^t\)-saturated graphs

This page was built for publication: Saturated graphs of prescribed minimum degree

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