MATH Seminar

Title: On $K_t$-Saturated Graphs
Defense: Dissertation
Speaker: Kinnari Amin of Emory University
Contact: Kinnari Amin, kinnari.amin@emory.edu
Date: 2010-07-07 at 4:00PM
Venue: MSC W301
Download Flyer
Abstract: Let $G$ be a graph on $n$ vertices. Let $H$ be a graph. Any $H$-free graph $G$ is called $H$-saturated if the addition of any edge $e \notin E(G)$ results in $H$ as a subgraph of $G$. The minimum size of an $H$-saturated graph on $n$ vertices is denoted by $sat(n, H)$. The edge spectrum for the family of graphs with property $P$ is the set of all sizes of graphs with property $P$.\\ \\ In this talk, I will present the results about the edge spectrum of $K_4$-saturated graphs. I will show that there is a $K_{4}$-saturated graph $G$ if and only if either $G$ is complete tripartite graph or $3n -8 \leq \|E(G)\| \leq \lfloor \frac{n^2 - n + 4}{3} \rfloor$. I will also classify all $K_{4}$-saturated graph with $\kappa(G)=2$ and $\kappa(G)=3$. I will present the result on the edge spectrum of $K_t$-saturated graphs for $t \geq 5$. I will show that, for $n \geq 5t-7$, there is an $(n, m) \mbox{ } K_t$-saturated graph $G$ if and only if $G$ is complete $(t-1)$-partite graph or $(t-1)(n-\frac{t}{2}) - 2 \leq m \leq \lfloor \frac{(t-2)n^2 - 2n + (t-2)}{2(t-1)} \rfloor + 1$.