\mychapter{Introduction}
\label{introduction}
\setcounter{page}{1}

%07/13/10


Extremal numbers first appeared in a $1907$ paper \cite{M1907} of Mantel dealing with triangles.  This was generalized to all complete graphs in a $1941$ paper \cite{T41} of Paul Tur\'{a}n.  In that paper, he determined the maximum number of edges in a $K_t$-free graph on $r$ vertices.  Furthermore, he found all $K_t$-free graphs with the maximum number of edges.  Since then extremal numbers have been studied intensively by numerous mathematicians and this study created a new branch of graph theory, called Tur\'{a}n-type extremal graph theory.  General extremal graph theory is the study of relations between various graph invariants, such as order, size, connectivity, minimum degree, maximum degree, chromatic number and diameter, as well as the values of these invariants which guarantee certain graph properties.  






\section{Definitions}
\label{Definitions}

A {\it graph} is a finite set of elements called vertices and a (possibly empty) set of $2$-element subsets of vertices called edges.  The {\it vertex set} of $G$ is denoted by $V(G)$, while the {\it edge set} of $G$ is denoted by $E(G)$.  The cardinality of the vertex set is called the {\it order} of the graph.  The cardinality of the edge set is called the {\it size} of the graph.  An $(n, m)-graph$ has order $n$ and size $m$.  Two vertices are called {\it adjacent vertices} if they are two end vertices of an edge.  Two edges are called {\it adjacent edges} if they share a commom end vertex.  A vertex and an edge are {\it incident} if the vertex is one end of the edge.  The {\it degree of a vertex v}, denoted by $d(v)$, in a graph $G$ is the number of edges incident with $v$.  By our definition, all graphs in this dissertation are simple graphs, i.e., finite graphs without loops (an edge joining a vertex to itself) or parallel edges (multiple edges sharing the same two end vertices).  
 

\begin{figure}[ht!]
\begin{center}
\epsfxsize 1in \epsfbox{graph.eps}
\caption{$G$}
\end{center}
\end{figure}


%The {\it complete graph} on $p$ vertices, denoted by $K_{p}$, contains an edge between every 
%pair of distinct vertices.  


A graph $G$ is called a {\it complete} graph if every two of its vertices are adjacent.  Hence, for any complete graph $G$ of order $n$, denoted by $K_n$, for all vertices $v \in V(G)$, $d(v) = n-1$.  A {\it path} graph $P_n$ is a sequence of alternating vertices and edges $v_1e_1 . . . e_{n-1}v_n$, where no vertices are repeated and consecutive elements are incident, so that $|V(P_n)| = |E(P_n)| + 1 = n$.  A graph $G$ whose vertex set $V(G)$ can be partitioned into two distinct subsets $X$ and $Y$ such that each edge of $G$ has one endpoint in $X$ and one endpoint in $Y$ is called a {\it bipartite} graph, denoted by $G(X \cup Y, E)$.  A bipartite graph $G(X \cup Y, E)$ is called a {\it complete bipartite} graph, denoted by $K_{k, n-k}$, where $|X| = k$ and $|Y| = n-k$, if for all vertices $x \in X$ and $y \in Y$, the edge $xy \in E(G)$.  A graph $G$ is {\it k-partite}, $k \geq 1$, if it is possible to partition $V(G)$ into $k$ subsets $V_1, V_2, . . . , V_k$ (called {\it partite sets}) such that every element of $E(G)$ joins a vertex of $V_i$ to a vertex of $V_j$, $i \neq j$.  A {\it complete k-partite} graph $G$ is a $k$-partite graph with partite sets $V_1, V_2, . . . , V_k$ having the added property that if $u \in V_i$ and $v \in V_j$, $i \neq j$, then $uv \in E(G)$.  The {\it join} $G = G_1 + G_2$ has vertex set $V(G) = V(G_1) \cup V(G_2)$ and edge set $E(G) = E(G_1) \cup E(G_2) \cup \{ uv|u \in V(G_1) \mbox{ and } v \in V(G_2) \}$.  Two vertices that are not adjacent in a graph $G$ are said to be {\it independent}.  A set $S$ of vertices is independent if every two vertices of $S$ are independent.  All other terms not defined here can be found in \cite{CL05}.







\section{Extremal Numbers}
\label{Extremal Numbers}

A graph $G$ is called an {\it $H$-saturated graph} if $G$ does not contain $H$ as a subgraph but the addition of any edge $e \notin E(G)$ produces $H$ as a subgraph.  The maximum number of edges in a $H$-saturated graph of order $n$ is called the {\it extremal number} and is denoted by $ex(n, H)$.  $ex(n, {\cal F})$ is defined to be the maximum number of edges in a $H$-saturated graph of order $n$ for any graph $H$ in the family of graphs ${\cal F}$.  $EX(n, H)$ is defined to be the set of $H$-saturated graphs of order $n$ of size $ex(n, H)$.  Extremal numbers have three nice properties.  Let ${\cal F}$ be a family of graphs. Then $ex(n, {\cal F})$ satisfies:


\begin{enumerate}
\item $ex(n, {\cal F}) \leq ex(n+1, {\cal F})$;

\item If ${\cal F}_1 \subset {\cal F}$ then $ex(n, {\cal F}_1 ) \geq ex(n, {\cal F})$;

\item If $H$ is a subgraph of $G$, then $ex(n, H) \leq ex(n, G)$.
\end{enumerate}  


In 1966, Erd\H{o}s, Stone, and Simonovits showed the following relationship between the chromatic number of a graph and the extremal number of a graph, known as the Erd\H{o}s-Stone-Simonovits Theorem.

\begin{theorem}
For any simple graph $G$
\begin{center}
$\lim_{n \to \infty} \frac{ex(n, G)}{n^2} = \frac{1}{2} \left( \frac{\chi(G) - 2}{\chi(G) - 1} \right)$
\end{center}
\end{theorem}


In 1941 \cite{T41}, Tur\'{a}n found the extremal number for complete graphs.

%\bigskip

\begin{theorem}
There is a unique extremal graph on $n$ vertices that is $K_{p+1}$-free, namely $T_{n,p}$.
 

\begin{figure}[ht!]
\begin{center}
\epsfxsize 3in \epsfbox{turang.eps}
\caption{$T_{n,p}$}
\end{center}
\end{figure}
\end{theorem}


The graph $T_{n,p}$ is called the Tur\'{a}n graph and is a complete almost balanced $p$-partite graph on $n$ vertices.  For example, the Tur\'{a}n graph which is a $K_4$-free graph on $10$ vertices has $33$ edges, namely a $K_{4,3,3}$ graph.  Note that the graph $K_{1,1,8}$ on $10$ vertices and $17$ edges is also a $K_4$-free graph.  Hence, there exists other saturated graph that are not extremal graphs.  





\section{Saturation Numbers}
\label{Saturation Numbers}

The {\it saturation number} of a graph is the minimum number of edges in an $H$-saturated graph of order $n$ and it is denoted by $sat(n, H)$.  $SAT(n, H)$ is defined to be the set of $H$-saturated graphs of order $n$ of size $sat(n, H)$.  A fundamental open problem for saturation numbers is to find a result that is an analogue of Erd\H{o}s-Stone-Simonovits Theorem.  In 1964 \cite{EHM64}, Erd\H{o}s, Hajnal and Moon determined the saturation number for $K_t$:  

\begin{theorem}
For $t \geq 3$, $sat(n, K_t) = (t-2)(n-1)-{t-2 \choose 2}.$
\end{theorem}

An example of a graph that attains this bound is $K_{t-2}+\overline{K}_{n-t+2}$, where $+$ denotes the join operation and $\overline{K}_{n-t+2}$ denotes $n-t+2$ independent vertices, and is the uniqe minimum sized saturated graph for $K_t$.  In fact, in \cite{EHM64} it is shown that $SAT(n, K_t)$ only contains $K_{t-2}+\overline{K}_{n-t+2}$.  In particular, $sat(n, K_3) = n-1$.  The {\it edge spectrum} for the family of graphs with property $P$ is the set of all sizes of graphs with property $P$.  In 1995, Barefoot et. al \cite{K395} proved the
following result about the edge spectrum of $K_{3}$-saturated graphs.  

\begin{theorem}\label{barefoot2}
Let $n \geq 5$ and $m$ be nonnegative integers.  There is an $(n, m) \mbox{ } K_{3}$-saturated graph if and only if $2n -5 \leq m \leq \lfloor (n-1)^2 / 4 \rfloor + 1$ or $m = k(n-k)$ for
some positive integer $k$.
\end{theorem}


Until now, this was the only result about the edge spectrum of saturated graphs.  The goal of this dissertation is to expand upon Theorem ~\ref{barefoot2} and determine the edge spectrum for any complete graph $K_t$, $t \geq 3$.  In 1986, K\'{a}szonyi and Tuza \cite{KT86} found the saturation number for paths, stars and matchings.  A {\it star} $S_{t+1}$ on $t+1$ vertices is simply the graph $K_{1,t}$.  A set of pairwise independent edges of $G$ is called a {\it matching} in $G$.  The graph $tK_2$ is simply a union of $t$ disjoint copies of the graph $K_2$. 


\begin{theorem}
$ \mbox{ } $
\begin{enumerate}
\item For $n \geq 3$, $sat(n, P_3) = \lfloor \frac{n}{2} \rfloor$.


\item For $n \geq 4$,
\begin{center}
$sat(n, P_4) = \left \{ 
\begin{array}{c l}
 n/2 & n \mbox{ even} \\
 (n+3)/2 & n \mbox{ odd}.
\end{array} 
\right.$
\end{center}


\item For $n \geq 5$, $sat(n, P_5) = \lceil \frac{5n-4}{6} \rceil$.


\item Let
\begin{center}
$a_k = \left \{ 
\begin{array}{c l}
 3*2^{t-1} - 2 & \mbox{ if } k = 2t\\
 4*2^{t-1} - 2 & \mbox{ if } k = 2t+1.
\end{array} 
\right.$
\end{center}
If $n \geq a_k$ and $k \geq 6$, then
\begin{center}
$sat(n, P_k) = n - \lfloor \frac{n}{a_k} \rfloor$. 
\end{center}

\end{enumerate}
\end{theorem}


\begin{theorem}
$ \mbox{ } $
\begin{center}
$sat(n, S_{k+1}) = \left \{ 
\begin{array}{c l}
 \left( \begin{array}{c} {k} \\ {2} \end{array} \right) + \left( \begin{array}{c} {n-k} \\ {2} \end{array} \right) & \mbox{ if } k+1 \leq n \leq k + \frac{k}{2} \\
 \lceil \frac{k-1}{2}n - \frac{k^2}{8} \rceil & \mbox{ if } k + \frac{k}{2} \leq n.
\end{array} 
\right.$
\end{center}
\end{theorem}


\begin{theorem}
$sat(n, tK_2) = 3t - 3$ for $n \geq 3t-3$.
\end{theorem}



Furthermore, K\'{a}szonyi and Tuza also gave a general bound on the saturation number for every graph in \cite{KT86}.  


\begin{theorem}
For every graph $F$, there exists a constant $c$ such that 
\linebreak $sat(n, F) < cn$.
\end{theorem}



Recently, G. Chen, R. J. Faudree, and R. Gould \cite{CFG8} found the saturation number for a book graph and a generalized book graph.  A {\it book} $B_p$ is a union of $p$ triangles sharing one edge.  A generalized book $B_{b,p}$ is the union of $p$ copies of $K_{b+1}$ sharing a common $K_b$.



\begin{theorem}
Let $n$ and $p$ be two positive integers such that $n \geq p^3 + p$.  Then,
\begin{center}
$sat(n, B_p) = \frac{1}{2} \left((p+1)(n-1) - \lceil \frac{p}{2} \rceil \lfloor \frac{p}{2} \rfloor + \theta(n, p)\right)$,
\end{center}
where $\theta(n, p) = \left \{ 
\begin{array}{c l}
 1 & \mbox{ if } p \equiv n - p/2 \equiv 0 (\bmod 2)\\
 0 & \mbox{ otherwise.}
\end{array} 
\right.$
\end{theorem}


Now define $f(n, b, p) = (p+2b-3)(n-b+1)- \lceil \frac{p}{2} \rceil \lfloor \frac{p}{2} \rfloor +(b-1)(b-2)+\theta(n, b, p)$, where 
\begin{center}
$\theta(n, b, p) = \left \{ 
\begin{array}{c l}
 1 & \mbox{ if } p \equiv n - p/2 - b \equiv 0 (\bmod 2)\\
 0 & n \mbox{ otherwise.}
\end{array} 
\right.$
\end{center}

\begin{theorem}
Let $n , b \geq 3$ and $p$ be three positive integers such that $n \geq 4(p+2b)^b$.  Then
\begin{center}
$sat(n, B_{b,p}) = \frac{1}{2} f(n, b, p)$.
\end{center}
\end{theorem}



Finding saturation number turns out to be hard in general.  Saturation numbers do not hold nice monotonicity properties, similar to extremal numbers listed in section ~\ref{Extremal Numbers}, as shown in the following examples.



\begin{enumerate}
\item  $sat(n, H)$ is not monotone for the order of the graph $H$, $n$.  

Note that $sat(n, K_3) = n-1$ and $sat(n+1, K_3) = n$.  Take a star on $n$ and $n+1$ vertices, respectively.  Hence, $sat(n, K_3) \leq sat(n+1, K_3)$.  


\begin{figure}[ht!]
\begin{center}
\epsfxsize 3in \epsfbox{ex1.eps}
\caption{$G \in SAT(n, P_4)$ with $n = 2k$ and $n = 2k-1$}
\end{center}
\end{figure}


Furthermore, $sat(2k, P_4) = k$.  Take $k$ pairs of vertices and join each pair by an edge.  Then, we obtain $sat(2k-1, P_4) = k+1$, by taking $k-2$ pairs of vertices joined by an edge and the remaining three vertices making a $K_3$.  Hence, with $n = 2k-1$, $sat(n, P_4)  > sat(n+1, P_4)$. 


\item $sat(n, {\cal F})$ in not monotone for family ${\cal F}$.  

Note that $sat(n, K_4) = 2n-3$ and $sat(n, \{K_3, K_4\}) = n-1$.  Hence, $sat(n, K_4) > sat(n, \{ K_3, K_4 \})$.  


\begin{figure}[ht!]
\begin{center}
\epsfxsize 4.5in \epsfbox{ex2.eps}
\caption{$G \in SAT(n, P_5)$ (Left graph, in blue) and $G \in SAT(n, \{ P_5, S_4 \})$ (Right graph, in magenta)}
\end{center}
\end{figure}


Let $n = 6k$ for some positive integer $k$.  Then, $sat(n, P_5) = n-( \frac{n-2}{6} + 1)$ (Figure 1.4) while $sat(n, \{ P_5, S_4 \}) = n-1$ (Figure 1.5).  So for large $n$, we have $sat(n, P_5) < sat(n, \{ P_5, S_4 \})$. 


\item $sat(n, H)$ is not monotone for graph $H$.

Note that $sat(n, K_3) = n-1$ and $sat(n, K_4) = 2n-3$.  Hence, $sat(n, K_3) \leq sat(n, K_4)$.

Furthermore, consider $K_4$ and the supergraph $H$ obtained by attaching an edge to $K_4$.   We know that $sat(n, K_4) = 2n-3$.  But for $H$ we have, $sat(n, H) \leq \frac{3}{2}n$.  So, $sat(n, K_4) \geq sat(n, H)$.



\begin{figure}[ht!]
\begin{center}
\epsfxsize 3in \epsfbox{ex3.eps}
\caption{Shows $sat(n, H) \leq \frac{3n}{2}$}
\end{center}
\end{figure}

\end{enumerate} 


Most graph properties are monotone.  And as we have just seen, being saturated is not a monotone property for graphs.  Hence, it is interesting and important to study the edge spectrum of a $H$-saturated graph for any graph $H$.  Complete graphs play a fundamental role in many aspects of graph theory, for example Ramsey Theory.  Hence, it is important to study the edge spectrum of $K_t$-saturated graphs.


