The saturation number of \(K_{3,3}\)

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\)-satu...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-11
Main Authors: Huang, Shenwei, Hui, Lei, Shi, Yongtang, Zhang, Junxue
Format: Article
Language:English
Subjects:
Graph theory
Saturation
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 \(\lfloor\frac{3n-5}{2}\rfloor\) 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 \(n\geq 5\). In this paper, we prove a conjecture of Pikhurko and Schmitt that \(sat(n, K_{3,3})=3n-9\) when \(n \geq 9\).
ISSN:2331-8422