Few H copies in F-saturated graphs

Jürgen Kritschgau, Abhishek Methuku, Michael Tait, Craig Timmons

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)320-348
Number of pages29
JournalJournal of Graph Theory
Volume94
Issue number3
DOIs
StatePublished - Jul 1 2020
Externally publishedYes

Keywords

  • extremal graph theory
  • graph saturation

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Few H copies in F-saturated graphs'. Together they form a unique fingerprint.

Cite this