MinimumK2, 3-Saturated Graphs

DOI10.1002/JGT.21767MaRDI QIDQ5495889zbMATH OpenOpenAlexFDO

Authors Ya-Chen Chen

Publication date 7 August 2014

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

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

zbMATH Keywords

3}\)-saturated graphs\(K_{2extremal graphsforbidden subgraphs

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: A graph is K_{2,3}-saturated if it has no subgraph isomorphic to K_{2,3}, but does contain a K_{2,3} after the addition of any new edge. We prove that the minimum number of edges in a K_{2,3}-saturated graph on n >= 5 vertices is sat(n, K_{2,3}) = 2n - 3.

Recommendations

• A note on minimum \(K_{2,3}\)-saturated graphs
• Minimum C_k-saturated graphs
• Minimum degree and the minimum size of \(K_2^t\)-saturated graphs
• Minimizing the number of edges in (P_k ∪ K₃)-saturated connected graphs
• Minimum \(t P_3\)-saturation graphs
• P_m-saturated graphs with minimum size
• A survey of minimum saturated graphs
• Minimizing the number of edges in \(K_{(s,t)}\)-saturated bipartite graphs
• Triangles in K_s-saturated graphs with minimum degree t
• tK\(_p\)-saturated graphs of minimum size

Cites work

• \(C_{3}\) saturated graphs
• A Problem in Graph Theory
• A survey of minimum saturated graphs
• All minimum \(C_{5}\)-saturated graphs
• Asymptotic results on saturated graphs
• Constructive upper bounds for cycle-saturated graphs of minimum size
• Cycle-saturated graphs of minimum size
• Cycle-saturated graphs with minimum number of edges
• 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
• Minimum degree and the minimum size of \(K_2^t\)-saturated graphs
• On generalized graphs
• Saturated r-uniform hypergraphs
• Saturated graphs with minimal number of edges
• Saturation numbers of books
• The Minimum Size of Saturated Hypergraphs
• The saturation function of complete partite graphs

Cited in

(27)

• On \((\mathrm{K}_t-e)\)-saturated graphs
• Minimum \(t P_3\)-saturation graphs
• The partite saturation number of spider
• scientific article; zbMATH DE number 1472200 (Why is no real title available?)
• scientific article; zbMATH DE number 1743768 (Why is no real title available?)
• \(K_{s,t}\)-saturated bipartite graphs
• Onk-saturated graphs with restrictions on the degrees
• scientific article; zbMATH DE number 1409250 (Why is no real title available?)
• Minimizing the number of edges in \(K_{(s,t)}\)-saturated bipartite graphs
• Triangles in K_s-saturated graphs with minimum degree t
• scientific article; zbMATH DE number 975388 (Why is no real title available?)
• Saturated graphs of prescribed minimum degree
• A note on minimum \(K_{2,3}\)-saturated graphs
• Minimizing the number of edges in (P_k ∪ K₃)-saturated connected graphs
• The saturation number of \(K_{3,3}\)
• Saturation numbers for linear forests $P_6 + tP_2$
• Linear saturation numbers of Berge-C₃ and Berge-C₄
• Saturation in Kneser graphs
• Minimum bull-saturated graphs
• Some results on the saturation number of graphs
• The saturation number for unions of four cliques
• Minimum saturated graphs for unions of cliques
• The saturation number of C₆
• (K₁ P_t)-saturated graphs with minimum number of edges
• The saturation number of W₄
• Saturation numbers of K₂ P_k
• Minimum degree and the minimum size of \(K_2^t\)-saturated graphs

This page was built for publication: MinimumK_{2, 3}-Saturated Graphs

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