Cycle-saturated graphs with minimum number of edges

DOI10.1002/JGT.21668MaRDI QIDQ4920660zbMATH OpenOpenAlexFDO

Authors Younjin Kim, Zoltán Füredi

Publication date 21 May 2013

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

cyclesextremal graphsgraphsminimal saturated graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: A graph $G$ is called $H$-saturated if it does not contain any copy of $H$, but for any edge $e$ in the complement of $G$ the graph $G+e$ contains some $H$. The minimum size of an $n$-vertex $H$-saturated graph is denoted by $sat(n,H)$. We prove ${\displaystyle }$sat(n,C_k) = n + n/k + O((n/k^2) + k^2)${\displaystyle }$ holds for all $ngeqkgeq3$, where $C_k$ is a cycle with length $k$. We have a similar result for semi-saturated graphs ${\displaystyle }$ssat(n,C_k) = n + n/(2k) + O((n/k^2) + k).${\displaystyle }$ We conjecture that our three constructions are optimal.

Recommendations

• Minimum C_k-saturated graphs
• Cycle-saturated graphs of minimum size
• On the number of edges in a minimum \(C_6\)-saturated graph
• Constructive upper bounds for cycle-saturated graphs of minimum size
• Constructive upper bounds for cycle-saturated graphs of minimum size

Cites work

• A Problem in Graph Theory
• A survey of minimum saturated graphs
• All minimum \(C_{5}\)-saturated graphs
• An extremal problem for sets with applications to graph theory
• An extremal problem for two families of sets
• Constructive upper bounds for cycle-saturated graphs of minimum size
• Cycle-saturated graphs of minimum size
• scientific article; zbMATH DE number 2192110 (Why is no real title available?)
• scientific article; zbMATH DE number 4185643 (Why is no real title available?)
• Minimum C₅‐saturated graphs
• On generalized graphs
• On maximal triangle‐free graphs
• Onk-saturated graphs with restrictions on the degrees
• Saturated graphs with minimal number of edges
• The saturation function of complete partite graphs
• tK\(_p\)-saturated graphs of minimum size

Cited in

(39)

• Cycle-saturated graphs of minimum size
• Minimizing the number of edges in \(\mathcal{C}_{\geq r} \)-saturated graphs
• Saturation problems in the Ramsey theory of graphs, posets and point sets
• Saturation numbers for disjoint stars
• Minimum \(t P_3\)-saturation graphs
• Minimum number of edges that occur in odd cycles
• \(C_{2k}\)-saturated graphs with no short odd cycles
• Graph cover-saturation
• The partite saturation number of spider
• Saturation number of \(tK_{l,l,l}\) in the complete tripartite graph
• Saturated Simple and 2-simple Topological Graphs with Few Edges
• Minimum C_k-saturated graphs
• scientific article; zbMATH DE number 4154477 (Why is no real title available?)
• Saturating Sperner families
• Saturation problems about forbidden 0-1 submatrices
• Saturation in the hypercube and bootstrap percolation
• MinimumK_{2, 3}-Saturated Graphs
• Weakly saturated hypergraphs and a conjecture of Tuza
• Constructive upper bounds for cycle-saturated graphs of minimum size
• Constructive upper bounds for cycle-saturated graphs of minimum size
• Saturation for the 3-uniform loose 3-cycle
• Saturation of Ordered Graphs
• Cycle Saturation in Random Graphs
• Linear saturation numbers of Berge-C₃ and Berge-C₄
• Sequence saturation
• Partite saturation number of cycles
• The saturation number of wheels
• Saturation results around the Erdős-Szekeres problem
• Saturation results around the Erdős-Szekeres problem
• Minimum saturated graphs without 4-cycles and 5-cycles
• The saturation number for unions of four cliques
• Minimum saturated graphs for unions of cliques
• Saturation numbers of bipartite graphs in random graphs
• The saturation number of C₆
• The saturation number of W₄
• The existence of C₄-saturated graphs having sizes close to the lower bound
• Saturation numbers of K₂ P_k
• Faces in girth-saturated graphs on surfaces
• Almost all permutation matrices have bounded saturation functions

This page was built for publication: Cycle-saturated graphs with minimum number of edges

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