%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This is mydata.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\cF}{\mathcal{F}}

\newcommand{\myname}{Kinnari V. Amin}
\newcommand{\myadvisor}{Ronald Gould, Ph.D.}
\newcommand{\mytitle}{On $K_t$-saturated Graphs}
\newcommand{\mydegree}{M.S., Georgia State University, 2004}
\newcommand{\thisyear}{2010}
\newcommand{\mydepartment}{Department of Mathematics and Computer Science}
%%% Can be 'Master of Science' or 'Doctor of Philosophy'
\newcommand{\thisdegree}{Doctor of Philosophy}
%%% type of thesis, can be 'thesis' or 'dissertation'
\newcommand{\typeofthesis}{dissertation}
\newcommand{\committeeone}{Michelangelo Grigni, Ph.D.}
\newcommand{\committeetwo}{Paul Horn, Ph.D.}
\newcommand{\committeethree}{Robert Roth, Ph.D.}
\newcommand{\deanofthegraduateschool}{Lisa A. Tedesco, Ph.D.}
%%% acknowledgements

\newcommand{\myacknowledgements}{The author wishes to thank Lord Krishna.  

The author wishes to thank her advisor, Goodrich C. White Professor, Dr. Ronald Gould.  Without his constant support, encouragement, patience, time, and kindness, this dissertation would not have been possible.  The author also wishes to thank her committee members, Dr. Michelangelo Grigni and Dr. Paul Horn, for their valuable suggestions and time.

The author wishes to thank her family for their love and support.  The author wishes to thank her husband, Vaibhav Amin, for his love, support and encouragement.  The author also wishes to thank her parents, Ushaben Patel and Rajendrakumar Patel, for their love and blessings and her siblings, Keyuri, Keshita, Monika, and Nishith, for their love and support.  The author wishes to thank her mother-in-law, Nitaben Amin, for her love, help, and blessings. 

Finally, the author wishes to thank all of her friends for supporting her all these past years.  The author wishes to thank all of her teachers and professors for their support and encouragement, especially Dr. Margaret Ehrlich, Dr. Frank Hall, Dr. Guantao Chen, and Mrs. Wei Conway.
}

%%% abstract
\newcommand{\myabstract}{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 called a saturation number, 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 dissertation, we show the edge spectrum of $K_4$-saturated graphs.  We also classify all $K_4$-saturated graphs of connectivity $2$ and $3$.  Furthermore, we 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$. 
}
%%% dedication
\newcommand{\mydedication}{
To my daughter Riya
}