The saturation number of K₃,3

DOI10.1016/J.DISC.2023.113794zbMATH Open1530.05089arXiv1910.04967MaRDI QIDQ6136680FDOQ6136680

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

Publication date: 17 January 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

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$.

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)

Cites Work

• Saturated graphs with minimal number of edges
• A Problem in Graph Theory
• The Minimum Size of Saturated Hypergraphs
• The saturation function of complete partite graphs
• A note on minimum \(K_{2,3}\)-saturated graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Minimum degree and the minimum size of \(K_2^t\)-saturated graphs
• Saturation numbers of books
• MinimumK_{2, 3}-Saturated Graphs

Cited In (1)

• Linear saturation numbers of Berge-\(C_3\) and Berge-\(C_4\)

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)