Abstract
A graph is (Formula presented.) -saturated if it is (Formula presented.) -free but the addition of any edge creates a copy of (Formula presented.). In this paper we study the function (Formula presented.) which is the minimum number of copies of (Formula presented.) that an (Formula presented.) -saturated graph on (Formula presented.) vertices may contain. This function is a natural saturation analogue of Alon and Shikhelman's generalized Turán problem, and letting (Formula presented.) recovers the well-studied saturation function. We provide a first investigation into this general function focusing on the cases where the host graph is either (Formula presented.) or (Formula presented.) -saturated. Some representative interesting behavior is: (a)For any natural number (Formula presented.), there are graphs (Formula presented.) and (Formula presented.) such that (Formula presented.).(b)For many pairs (Formula presented.) and (Formula presented.), we show (Formula presented.). In particular, we prove that there exists a triangle-free (Formula presented.) -saturated graph on (Formula presented.) vertices for any (Formula presented.) and large enough (Formula presented.).(c) (Formula presented.), (Formula presented.), and (Formula presented.). We discuss several intriguing problems that remain unsolved.
Original language | English (US) |
---|---|
Pages (from-to) | 320-348 |
Number of pages | 29 |
Journal | Journal of Graph Theory |
Volume | 94 |
Issue number | 3 |
DOIs | |
State | Published - Jul 1 2020 |
Externally published | Yes |
Keywords
- extremal graph theory
- graph saturation
ASJC Scopus subject areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics