The existence of \(C_{4}\)-saturated graphs having sizes close to the lower bound

Pennapa Chodok1,2, Nuttanon Songsuwan2,3, Pawaton Kaemawichanurat1,2
1Department of Mathematics, Faculty of Science, King Mongkut’s University of Technology Thonburi, Bangkok, Thailand
2Mathematics and Statistics with Applications (MaSA)
3Faculty of Science at Sriracha, Kasetsart University, Sriracha Campus, Chonburi, Thailand

Abstract

A graph \(G\) is \(H\)-saturated if \(G\) does not have \(H\) as a subgraph but \(G + uv\) has at least one copy of \(H\) for any edge \(uv \notin E(G)\). The smallest number of edges of all \(H\)-saturated graphs of order \(n\) is called \(H\)-saturation number and is denoted by \(sat(n; H)\). In this paper, we establish the existence of \(C_{4}\)-saturated graphs with prescribed the number of edges in some length that is close to \(sat(n; C_{4})\).

Keywords: extremal number, even cycle, saturation number, saturation spectrum