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

minimum degreecomplete bipartite graphssaturation numbers

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3414346 (Why is no real title available?)
• scientific article; zbMATH DE number 4185643 (Why is no real title available?)
• A Problem in Graph Theory
• A note on minimum \(K_{2,3}\)-saturated graphs
• 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

(9)

• Some results on the saturation number of graphs
• The saturation number of C₆
• Linear saturation numbers of Berge-C₃ and Berge-C₄
• (K₁ P_t)-saturated graphs with minimum number of edges
• The saturation number of W₄
• Saturation in Kneser graphs
• Minimum bull-saturated graphs
• Minimum saturated graphs for unions of cliques
• The saturation number for unions of four cliques

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)