Generalized saturation problems for cliques, paths, and stars

Abstract

A graph $G$ is $F$-saturated if it does not contain any copy of $F$, but the addition of any missing edge in $G$ creates at least one copy of $F$. Inspired by work of Alon and Shikhelman regarding a similar question for $F$-free graphs, Kritschgau, Methuku, Tait, and Timmons introduced the parameter of ${\text{sat}}_H(n,F)$ to denote the minimum number of copies of some subgraph $H$ in an $F$-saturated graph on $n$ vertices. In this paper, we address this generalized saturation problem with special focus on ${\text{sat}}_{K_r}(n,S_t)$ and ${\text{sat}}_{S_r}(n,S_t)$ This relates to recent work by Chakraborti and Loh regarding ${\text{sat}}_{K_r}(n,K_t)$ and by Ergemlidze, Methuku, Tait, and Timmons regarding ${\text{sat}}_{S_r}(n,K_t)$. We also provide some results regarding paths and arbitrary trees.

16 pages, 5 figures