Minimizing the number of complete bipartite graphs in a ks-saturated graph

Beka Ergemlidze, Abhishek Methuku, Michael Tait, Craig Timmons

Research output: Contribution to journalArticlepeer-review

Abstract

A graph is F-saturated if it does not contain F as a subgraph but the addition of any edge creates a copy of F. We prove that for s ≥ 3 and t ≥ 2, the minimum number of copies of K1,t in a Ks-saturated graph is Θ (nt/2). More precise results are obtained in the case of K1,2, where determining the minimum number of K1,2's in a K3-saturated graph is related to the existence of Moore graphs. We prove that for s ≥ 4 and t ≥ 3, an n-vertex Ks-saturated graph must have at least Cnt/5+8/5 copies of K2,t, and we give an upper bound of O(nt/2+3/2). These results answer a question of Chakraborti and Loh on extremal Ks-saturated graphs that minimize the number of copies of a fixed graph H. General estimates on the number of Ka,b's are also obtained, but finding an asymptotic formula for the number Ka,b's in a Ks-saturated graph remains open.

Original languageEnglish (US)
Pages (from-to)793-807
JournalDiscussiones Mathematicae - Graph Theory
Volume43
Issue number3
DOIs
StatePublished - 2023
Externally publishedYes

Keywords

  • extremal graph theory
  • graph saturation

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Minimizing the number of complete bipartite graphs in a ks-saturated graph'. Together they form a unique fingerprint.

Cite this