The saturation number of K₃,3

DOI10.1016/J.DISC.2023.113794MaRDI QIDQ6136680zbMATH OpenFDO

Authors Shenwei Huang, Hui Lei, Yongtang Shi, Junxue Zhang

Publication date 17 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

complete bipartite graphsminimum degreesaturation numbers

Mathematics Subject Classification ID

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

Abstract: A graph $G$ is called $F$-saturated if $G$ does not contain $F$ as a subgraph (not necessarily induced) but the addition of any missing edge to $G$ creates a copy of $F$. The saturation number of $F$, denoted by $sat(n,F)$, is the minimum number of edges in an $n$-vertex $F$-saturated graph. Determining the saturation number of complete partite graphs is one of the most important problems in the study of saturation number. The value of $sat(n,K_{2,2})$ was shown to be $lfloorfrac3n-52floor$ by Ollmann, and a shorter proof was later given by Tuza. For $K_{2,3}$, there has been a series of study aiming to determine $sat(n,K_{2,3})$ over the years. This was finally achieved by Chen who confirmed a conjecture of Bohman, Fonoberova, and Pikhurko that $sat(n,K_{2,3})=2n-3$ for all $ngeq5$. In this paper, we prove a conjecture of Pikhurko and Schmitt that $sat(n,K_{3,3})=3n-9$ when $ngeq9$.

Recommendations

• MinimumK_{2, 3}-Saturated Graphs
• A note on minimum \(K_{2,3}\)-saturated graphs
• Saturation number of \(tK_{l,l,l}\) in the complete tripartite graph
• \(K_{s,t}\)-saturated bipartite graphs
• Saturation numbers in tripartite graphs

Cites work

• A note on minimum \(K_{2,3}\)-saturated graphs
• A Problem in Graph Theory
• scientific article; zbMATH DE number 3414346 (Why is no real title available?)
• scientific article; zbMATH DE number 4185643 (Why is no real title available?)
• Minimum degree and the minimum size of \(K_2^t\)-saturated graphs
• MinimumK_{2, 3}-Saturated Graphs
• 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

(11)

• 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 for linear forests P₅ P₄ tP₂
• Saturation numbers of K₂ P_k

This page was built for publication: The saturation number of \(K_{3,3}\)

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