Partial Saturation Numbers of Graphs

Abstract

Given a fixed simple graph $H$, a simple graph $G$ is called $H$-saturated if $G$ is $H$-free, but the addition of any edge $e \in E(\overline{G})$ creates a copy of $H$. The saturation number of $H$, denoted $\sat(n,H)$, is the minimum number of edges of an $H$-saturated graph $G$ on $n$ vertices. If $G$ is not necessarily $H$-free, but the addition of any edge $e \in E(\overline{G})$ creates a new copy of $H$, then $G$ is called partially $H$-saturated. The partial saturation number of $H$, denoted $\psat(n,H)$, is the minimum size of a partially $H$-saturated graph on $n$ vertices. In this dissertation, we explore the relationship between $\sat(H,n)$ and $\psat(n,H)$ and determine $\psat(n,H)$ for various classes of graphs $H$.

We first show that $\psat(n,H)=\sat(n,H)$ for every graph $H$ of order at most 4, with only one exception. In the case $H=C_4$, we characterize all minimum partially $C_4$-saturated graphs. For a double star on $s+t$ vertices, with $3 \leq s < t$, we completely determine $\psat(n, S_{s,t})$ when $n$ is large enough. We study the partial saturation number of triangle-free graphs and provide a nearly sharp lower bound. For a path $P_k$, we establish the exact value of $\psat(n,P_k)$ when $n \geq \Big \lfloor \frac{3k-3}{2} \Big \rfloor$. We observe that for $k \geq 6$, $ \lim_{n\to\infty} \frac{\sat(n,P_k)-\psat(n,P_k)}{n} >0$. Finally, we characterize all triangle-free graphs $H$ such that $\lim_{n\to\infty} \frac{\psat(n,H)}{n}$ is minimized.