\mychapter{$K_{t}$-Saturated Graphs}
\label{chapter:K_t}


%07/13/10


It is known that any $K_{t}$-saturated graph has at least 
$(t-2)(n-1) - \left( \begin{array}{c} {t-2} \\ {2} \end{array} \right)$ edges and at most 
$\lfloor \frac{(t-2)n^2}{2(t-1)} \rfloor$ edges and these bounds are sharp.  The emphasis 
of this chapter will be on determining the sizes of $K_{t}$-saturated graphs of order $n$, 
that is the edge spectrum of $K_t$-saturated graphs.  We prove 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$.   We show the lower bound of the interval for small minimum degree and chromatic number of a graph first.  Then we apply a result by Duffus and Hanson \cite{dh86} for $\delta(G) \geq t+2$ and $\chi(G) \geq t+1$.  We again apply the result by Hanson and Toft \cite{ht91} to show the upper bound of our result.  




\section{Lower Bound for $K_{t}$-saturated Graphs}
\label{sec:LowerBoundfor$K_{t}$-saturatedGraphs}


In trying to establish a lower bound on the size of a $K_t$-saturated graph that is not 
isomorphic to the Erd\H{o}s, Hajnal, and Moon graph $K_{t-2} + \overline{K_{n-t+2}}$, 
the chromatic number of the graph in question will be very important.  Also, convexity 
considerations will play a role in minimizing the size of the graph.  We develop a 
series of results based upon the chromatic number and subsequent minimum degree of the graph.  First, we make the following observation.  



\begin{proposition} \label{prop}
Let $G$ be a $K_{t}$-saturated graph.  Then $G$ is $(t-2)$-connected.
\end{proposition}
\proof
Let $G$ be a $K_{t}$-saturated graph.  Suppose $G$ is not $(t-2)$-connected.  Let $U = \{ u_1, u_2, . . . , u_{t-3} \}$ be the cut set and let $A$ and $B$ be components of $G-U$ with $x \in V(A)$ and $y \in V(B)$.  Now the addition of the edge $xy$ creates a $K_{t}$.  A contradiction as $\{ x, y \} \cup U$ forms at most a $K_{t-1}$.
\qed



\begin{theorem} \label{LB1}
If $G$ is a complete $(t-1)$-partite $K_t$-saturated graph and $G$ is not isomorphic to $K_{t-2} + \overline{K_{n-t+2}}$, then $|E(G)| > (t-1)(n - \frac{t}{2}) - 2$.
\end{theorem}
\proof
Let $G$ be a complete $(t-1)$-partite $K_t$-saturated graph of order $n \geq t+1$.  Let $C_1, C_2, C_3, . . . , C_{t-1}$ be the $(t-1)$ partite sets of $G$.  Suppose  $G$ is not isomorphic to $K_{t-2} + \overline{K_{n-t+2}}$. Now, by the Erd\H{o}s, Hajnal, Moon Theorem, $G$ will have the minimum number of edges if $(t-2)$ sets, say $1, 2, . . . , t-2$, each contain one vertex and the $(t-1)$-st set contains the remaining vertices.  Since $G$ is not isomorphic to 
$K_{t-2} + \overline{K_{n-t+2}}$, at least one of the $(t-2)$ sets contains more than one 
vertex.  In fact, $G$ will have the minimum number of edges if exactly one of the $(t-2)$
sets contains exactly two vertices. Without loss of generality, say set $1$ contains two
vertices.  Now, the number of edges in $G$ is as follows:

\begin{eqnarray*}
|E(G)| & = & \frac{1}{2} ((t-3)(n-1) + 2(n-2) + (n-t+1)(t-1)) \\ & = & \frac{1}{2} ( 2nt - 2n + t - t^2 - 2) \\ & = & nt - n - \frac{t(t-1)}{2} - 1 \\ & = & (t-1) (n - \frac{t}{2}) - 1 \\ & > & (t-1)(n - \frac{t}{2}) - 2.
\end{eqnarray*}
\qed






Note that, any $(t-1)$-partite graph that is $K_t$-saturated must be a complete $(t-1)$-partite graph.  Hence, the case $\chi(G) = t-1$ is handled.  Next, make the following two useful observations about $K_{t}$-saturated graphs. 



\begin{enumerate}
\item The neighborhood of every vertex contains a copy of $K_{t-2}$.

\item For every pair of vertices $u, v \in V(G)$, $uv \notin E(G)$ if and only 
if there exists a copy of $K_{t-2}$ in their common neighborhood.
\end{enumerate} 






\begin{theorem} \label{LB2}
Let $G$ be a $K_t$-saturated graph with $\chi(G) = t$, then $|E(G)| \geq (t-1)(n - \frac{t}{2}) - 2$.
\end{theorem}
\proof
Let $G$ be a $K_t$-saturated graph of order $n$ with $\chi(G) = t$.  Let $C_1, C_2,
. . . , C_t$ be $t$ independent sets based on the $t$ color classes.  Suppose  $G$ has
the minimum number of edges. Now $G$ will have minimum number of edges if $(t-1)$ sets, say $C_1, C_2, . . . , C_{t-1}$, will contain exactly one vertex each and set $C_t$ will contain the remaining $n-t+1$ vertices.  It is easy to see that if you increase the number of vertices in any of the sets $C_1, C_2, . . . , C_{t-1}$, you increase the number of edges as $G$ is $K_t$-saturated and $\chi(G) = t$.  Some of these graphs will not satisfy the given conditions and can be ignored.  Now by observation 1, $G$ contains at least one copy of $K_{t-2}$ and by observation 2, every pair of nonadjacent vertices must be adjacent to a copy of $K_{t-2}$.  So without loss of generality, say sets $C_1, C_2, . . . , C_{t-2}$ make up $K_{t-2}$.  Since $G$ is a $K_t$-saturated graph, every vertex of the set $C_t$ must be adjacent to the vertices in sets $C_1, C_2, . . . , C_{t-2}$.  Hence, now either the vertex in set $C_{t-1}$ is adjacent to all the vertices of sets $C_1, C_2, . . . , C_{t-2}$ or all the vertices of the set $C_t$ and $t-3$ sets of the remaining $t-2$ sets $C_1, C_2, . . . , C_{t-2}$.  In either case, $\chi(G)=t-1$.  Hence, $G$ cannot have $t$ partite sets with $t-1$ partite sets of the size $1$ and one partite set of size $n-t+1$.


So now suppose $G$ has exactly one vertex in $t-2$ sets, say $C_1, C_2, . . . , C_{t-2}$, two
vertices in one set, say $C_{t-1}$, and the remaining $n-t$ vertices in one set, say $C_t$.  
As stated earlier, by observation 1, $G$ contains at least one copy of $K_{t-2}$
and by observation 2, every pair of nonadjacent vertices must be adjacent to a copy of $K_{t-2}$.  So without loss of generality, say sets $C_1, C_2, . . . , C_{t-2}$ make up a $K_{t-2}$.  Since $G$ is a $K_t$-saturated graph, one of the following two options for the remaining edges must hold:


\begin{enumerate}
\item Every vertex of the set $C_{t-1}$ is adjacent to every vertex of the set $C_t$ and every
  vertex of the sets $C_{t-1}$ and $C_t$ is adjacent to exactly $t-3$ of the $t-2$ sets.

\item Every vertex of the sets $C_{t-1}$ and $C_t$ is adjacent to every vertex of the sets $C_1,
  C_2, . . . , C_{t-2}$ and there are no edges between vertices of the sets $C_{t-1}$ and $C_t$. 
\end{enumerate}
   

Again, in both cases, $\chi(G) = t-1$.  Hence, $G$ cannot have $t$ such color classes.


Hence, assume $G$ has exactly one vertex in $t-3$ sets, say $C_1, C_2, . . . , C_{t-3}$, exactly two
vertices in two sets, say $C_{t-2}, C_{t-1}$, and the remaining $n-t-1$ vertices in one set, say
$C_t$.  Let $V(C_i)= v_i$ for $1 \leq i \leq t-3$, $V(C_{t-2}) = \{x_1, x_2 \}$, $V(C_{t-1}) = \{y_1, y_2
\}$, and $V(C_t) = \{w_1, w_2, . . . , w_{n-t-1} \}$.   Now from an argument similar to the ones above, 
we have $v_iv_j \in E(G)$ for all $1 \leq i < j \leq t-3$, $w_ix_2, w_iy_2 \in E(G)$ and $w_iv_j \in E(G)$ 
for $1 \leq i \leq n-t-1$, $1 \leq j \leq t-3$. Also, $x_iv_j, y_iv_j \in E(G)$ for $i = 1, 2$ and 
$1 \leq j \leq t-3$, $x_1y_1, x_1y_2, x_2y_1 \in E(G)$.  Hence, the number of edges in $G$ is 

\begin{eqnarray*}
|E(G)| & = & \frac{(t-3)(t-4)}{2}+ 2(n-t-1) + (n-t-1)(t-3) + 2(t-3) + \\ & & 2(t-3) + 3 \\ & = & n(t-1) +
\frac{-t^2+t-4}{2} \\ & = & n (t -1) - \frac{t(t-1)}{2} - 2 \\ & = & (t-1) (n - \frac{t}{2}) - 2.
\end{eqnarray*}
\qed





We next consider the following.

\begin{lemma}\label{LB3lemma}
If $G$ is a $K_{t}$-saturated graph with $\chi(G) \geq t+1$, then $\delta(G) \geq t$.
\end{lemma}
\proof
Let $G$ be a $K_t$-saturated graph of order $n$ with $\chi(G) \geq t+1$.  Then by observation 1, $\delta(G) \geq t-2$.  Assume $\delta(G) = t-2$.  Let $v \in V(G)$ such that $d(v) = t-2$.  Let $N(v) = \{ v_1, v_2, . . . . , v_{t-2} \}$ and $W = V(G) - \{ v \cup N(v) \}$.  Then by observation 1, $\langle N(v) \rangle \cong K_{t-2}$.  Then by observation 2, every vertex $u \in W$, $uv_i \in E(G)$ for $1 \leq i \leq t-2$.  Hence, we can color vertices $\{ v_1, v_2, . . . . , v_{t-2} \}$ with colors $\{1, 2, . . . , t-2\}$, respectively, and the remaining vertices $v$ and $u \in W$ by color $t-1$. Now $\chi(G) = t-1$, a contradiction.

Assume $\delta(G) = t-1$.  Let $v \in V(G)$ such that $d(v) = t-1$.  Let $N(v) = \{ v_1, v_2, . . . . , v_{t-1} \}$ and $W = V(G) - \{v \cup N(v) \}$.  Then by observation 1, $\langle N(v) \rangle$ contains a copy of $K_{t-2}$.  Then $\langle N(v) \rangle$ contains either one or two copies of $K_{t-2}$.  Suppose $\langle N(v) \rangle$ contains exactly one copy of $K_{t-2}$, say $K_{t-2} \cong \langle v_1, v_2, . . ., v_{t-2} \rangle$. Then by observation 2, every vertex $u \in W$, $uv_i \in E(G)$ for $1 \leq i \leq t-2$.  Hence, $W$ must be an independent set.  Furthermore, we note that $v_{t-1}$ must be adjacent to each vertex of $W$ for otherwise, by observation 2, $v_{t-1}$ is adjacent to $v_1, v_2, . . . , v_{t-2}$, producing a $K_t$, a contradiction.  Without loss of generality, $v_jv_{t-1} \in E(G)$ for $1 \leq j \leq t-4$ as $N(v)$ contains exactly one copy of $K_{t-2}$.  Then the addition of the edge $v_{t-1}v_{t-3}$ should create a $K_t$.  Since $N(v_{t-1}) \cap N(v_{t-3}) = W \cup \{v, v_1, v_2, . . . , v_{t-4} \}$, the addition of the edge $v_{t-1}v_{t-3}$  creates only a $K_{t-1}$, contradiction.

So suppose $\langle N(v) \rangle$ contains two copies of $K_{t-2}$, say $K^1_{t-2} \cong \langle v_1, v_2, . . ., v_{t-2} \rangle$ and $K^2_{t-2} \cong \langle v_2, v_3, . . ., v_{t-1} \rangle$.  Then by observation 2, every vertex $u \in V(G) - \{ v \cup N(v) \}$, $uv_i \in E(G)$ for $1 \leq i \leq t-2$ or $uv_i \in E(G)$ for $2 \leq i \leq t-1$ or $uv_i \in E(G)$ for $1 \leq i \leq t-1$.  Define 


\begin{eqnarray}
&& A = \{ u \in V(G) - \{ v \cup N(v) \} | uv_i \in E(G), i = 1, 2, . . ., t-2 \}, \nonumber\\
&& B = \{ u \in V(G) - \{ v \cup N(v) \} | uv_i \in E(G), i = 2, 3, . . ., t-1 \}, \nonumber\\
&& C = \{ u \in V(G) - \{ v \cup N(v) \} | uv_i \in E(G), i = 1, 2, . . ., t-1 \}. \nonumber
\end{eqnarray}


%\begin{displaystyle}
%$A = \{ u \in V(G) - \{ v \cup N(v) \} | uv_i \in E(G), 1 \leq i \leq t-2 \}$,  & &
%$B = \{ u \in V(G) - \{ v \cup N(v) \} | uv_i \in E(G), 2 \leq i \leq t-1 \}$, & &
%$C = \{ u \in V(G) - \{ v \cup N(v) \} | uv_i \in E(G), 1 \leq i \leq t-1 \}$. 
%\end{displaystyle}


Note that if there is an edge in either of the sets, $A, B, C$, then $K_t$ already exists as the vertices in these sets are adjacent to at least one copy of $K_{t-2}$.  Hence, the sets $A, B, C$ are independent sets. Furthermore, there is no edge between vertices of the sets $A$ and $C$, otherwise $K_t$ already exists.  Similarly, there is no edge between vertices of the sets $B$ and $C$. 

Claim: $\langle A \cup B \rangle$ is a complete bipartite graph.

Suppose not.  Then there exists vertices $u \in A$ and $v \in B$ such that $uv \notin E(G)$.  Now addition of the edge $uv$ should create a $K_t$.  Since $N(u) \cap N(v) = \{ v_2, v_3, . . . , v_{t-2} \}$, addition of the edge $uv$ creates a $K_{t-1}$, a contradiction.  Hence, $\langle A \cup B \rangle$ is a complete bipartite graph. 

Now color the vertex $v$ with color $1$, vertex $v_{t-1}$ with color $2$, and vertices $v_1, v_2, . . . , v_{t-2}$ with colors $2, 3, . . . , t-1$, respectively.  Also, color the sets $A$ and $C$ with color $1$ and color the set $B$ with color $t$.  Hence, $\chi(G) = t$, a contradiction.  Hence, $\delta(G) \geq t$.
\qed







\begin{lemma}\label{L1}
If $G$ is a $K_t$-saturated graph with $\delta(G) \geq t$, $\chi(G) \geq t+1$, and $v \in V(G)$ 
with $d(v) = \delta(G)$, then $N(v)$ contains at least three copies of $K_{t-2}$.
\end{lemma}
\proof
Assume $G$ is a $K_t$-saturated graph with $\delta(G) \geq t$ and $\chi(G) \geq t+1$.  
Let $v \in V(G)$ with $d(v) = \delta(G)$.  
Let $N(v) = \{v_1, v_2, . . . v_{\delta(G)}\}$, $W = \{v\} \cup N(v)$ and $U = V(G) - W$.


Suppose $N(v)$ contains exactly one copy of $K_{t-2}$.
Without loss of generality, let $K_{t-2} \cong \langle v_1, v_2, . . . ,v_{t-2} \rangle$.
As $G$ is a $K_t$-saturated graph and there is exactly one copy of $K_{t-2}$, $v_{t-1}$ is 
adjacent to at most $t-4$ of the vertices $v_1, v_2, . . . , v_{t-2}$, say 
$v_1, v_2, . . . , v_{t-4}$.  Also, for every $u \in U$, $uv_i \in E(G)$, 
for $i = 1, 2, . . . , t-2$.  Hence, $U$ is an independent set.  Now addition of the edge 
$v_{t-2}v_{t-1}$ must create a $K_t$.  But this fails as only a $K_{t-1}$ is formed containing 
$v_1, v_2, . . . , v_{t-4}, v_{t-2}, v_{t-1}$ and either $v$ or at most one of the vertices 
from $U$.


Now suppose $N(v)$ contains exactly two copies of $K_{t-2}$. 
Then without loss of generality, $K_{t-2}^{(1)} \cong \langle v_1, v_2, . . . , v_{t-2} \rangle$ 
and $K_{t-2}^{(2)} \cong  \langle v_2, v_3, . . . , v_{t-1} \rangle$.  As seen above, $v_{t}$ is 
adjacent to at most $t-4$ vertices of $v_1, v_2, . . . , v_{t-1}$, say $v_2, v_3, . . . , v_{t-3}$.
Then for every $u \in U$, $uv_i \in E(G)$ for $i = 1, 2, . . . , v_{t-2}$ or $i = 2, 3, . . . , v_{t-1}$, 
or $i = 1, 2, . . . , v_{t-1}$, or $i = 1, 2, . . . , \delta(G)$.
Let 


\begin{eqnarray}
&& A = \{u \in U | uv_i \in E(G) \mbox{ for } i = 1, 2, . . . , t-2\}, \nonumber\\
&& B = \{u \in U | uv_i \in E(G) \mbox{ for } i = 2, 3, . . . , t-1\}, \nonumber\\
&& C = \{u \in U | uv_i \in E(G) \mbox{ for } i = 1, 2, . . . , t-1\}, \nonumber\\
&& D = \{u \in U | uv_i \in E(G) \mbox{ for } i = 1, 2, . . . , \delta(G)\}. \nonumber
\end{eqnarray}


It can be easily seen that the sets $A$, $B$, $C$, and $D$ are independent sets.  Furthermore, $A \cup B$ forms a complete 
bipartite graph, see Lemma ~\ref{LB3lemma}.  Also, there is no edge between two vertices from $A$ and $C$, $A$ and $D$, $B$ and $C$, $B$ and $D$, and $C$ and $D$, otherwise $K_t$ already exists.  Now addition of the edge $v_1v_t$ must create a $K_t$.  But this fails as only a $K_{t-1}$ is created containing the vertices $v_2, v_3, . . . , v_{t-3}$ and either $v$ or at most one vertex from $C \cup D$.  Similarly, we obtain a contradiction if two copies of $K_{t-2}$ intersect in less than $t-3$ vertices.  Hence, $N(v)$ contains at least three copies of $K_{t-2}$.
\qed







\begin{lemma}\label{L2}
If $G$ is a $K_t$-saturated graph with $\delta(G) = t$, $\chi(G) = t+1$, and $v \in V(G)$ with $d(v) = \delta(G)$, then $N(v)$ contains exactly three copies of $K_{t-2}$.
\end{lemma}
\proof
Assume $G$ is a $K_t$-saturated graph with $\delta(G) = t$.  
Let $v \in V(G)$ with $d(v) = \delta(G) = t$.  
Let $N(v) = \{v_1, v_2, . . . v_{t}\}$, $W = \{v\} \cup N(v)$ and $U = V(G) - W$.  
Then by Lemma ~\ref{L1}, $N(v)$ contains at least three copies of $K_{t-2}$.  
Let 


\begin{eqnarray}
&& K_{t-2}^{(1)} \cong \langle v_1, v_2, . . . , v_{t-2} \rangle, \nonumber\\
&& K_{t-2}^{(2)} \cong \langle v_2, v_3, . . . , v_{t-1} \rangle, \nonumber\\
&& K_{t-2}^{(3)} \cong \langle v_2, v_3, . . . , v_{t-2}, v_{t} \rangle. \nonumber
\end{eqnarray}



%$K_{t-2}^{(1)} \cong \langle v_1, v_2, . . . , v_{t-2} \rangle$, 
%$K_{t-2}^{(2)} \cong \langle v_2, v_3, . . . , v_{t-1} \rangle$, and 
%$K_{t-2}^{(3)} \cong \langle v_2, v_3, . . . , v_{t-2}, v_{t} \rangle$.


  
Now by observation 2, every $u \in U$ is adjacent to at least one copy of $K_{t-2}$.  
So define the following sets as in Figure 3.1:


\begin{eqnarray}
&& A = \{u \in U | uv_i \in E(G) \mbox{ for } i = 1, 2, . . . , t-2\} \mbox{ (green)}, \nonumber\\
&& B = \{u \in U | uv_i \in E(G) \mbox{ for } i = 2, 3, . . . , t-1\} \mbox{ (red)}, \nonumber\\
&& C = \{u \in U | uv_i \in E(G) \mbox{ for } i = 2, 3, . . . , t-2, t\} \mbox{ (blue)}, \nonumber\\
&& D = \{u \in U | uv_i \in E(G) \mbox{ for } i = 1, 2, . . . , t\} \mbox{ (black)}. \nonumber
\end{eqnarray}


%$A = \{u \in U | uv_i \in E(G) \mbox{ for } i = 1, 2, . . . , t-2\}$ (green), 
%$B = \{u \in U | uv_i \in E(G) \mbox{ for } i = 2, 3, . . . , t-1\}$ (red), 
%$C = \{u \in U | uv_i \in E(G) \mbox{ for } i = 2, 3, . . . , t-2, t\}$ (blue), and 
%$D = \{u \in U | uv_i \in E(G) \mbox{ for } i = 1, 2, . . . , t\}$ (black), as in Figure 1.


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


Then the sets $A$, $B$, $C$, and $D$ are independent sets, otherwise a $K_{t}$ already exists.  
Also, as seen earlier, $A \cup B$ and $A \cup C$ are complete bipartite graphs.  
Furthermore, there is no edge between the vertices of the sets $A$ and $D$, $B$ 
and $C$, $B$ and $D$, and $C$ and $D$, otherwise a $K_t$ already exists.  
Also, note that none of the sets $A, B, C$ can be adjacent to more than one 
copy of $K_{t-2}$, otherwise a $K_t$ already exists.  
Now it can be easily checked that $G$ is a $K_t$-saturated graph.  

Furthermore, it can be easily seen that $N(v)$ cannot contain more copies of $K_{t-2}$ 
otherwise $K_t$ already exists containing the vertex $v$ and vertices from $N(v)$.  
Hence, $N(v)$ contains exactly three copies of $K_{t-2}$.
\qed







\begin{lemma}\label{L3}
If $G$ is a $K_t$-saturated graph with $\delta(G) = t$ and $\chi(G) \geq t+1$, 
then $|E(G)| \geq (t-1)(n - \frac{t}{2}) - 2$.
\end{lemma}
\proof
Suppose $G$ is a $K_t$-saturated graph with $\delta(G) = t$ and $\chi(G) \geq t+1$.
Then by Lemma ~\ref{L2}, $N(v)$ contains exactly three copies of $K_{t-2}$ and we 
have the graph in Figure 1, as shown in Lemma ~\ref{L2}.  Note that we obtain minimum 
number of edges in the graph if $|A| = |B| = |C| = 1$, by convexity.  Now, the 
minimum number of edges in the graph is


\begin{eqnarray*}
|E(G)| & \geq & t + \left( \begin{array}{c} {t-3} \\ {2} \end{array} \right) 
+ 3(t-3) + 3(t-2) + 2 + t(n-t-4) \\ 
& = & \frac{(t-3)(t-4)}{2} + 3t + nt - t^2  - 13  \\ 
& = & n (t -1) - \frac{t(t-1)}{2} - 2 + n - t - 5\\ 
& = & (t-1) (n - \frac{t}{2}) - 2 + n - t - 5.
\end{eqnarray*}


So $n - t - 5 \geq 0$ if $n \geq t + 5$.  Hence, we have $|E(G)| \geq (t-1)(n - \frac{t}{2}) - 2$.
\qed







\begin{lemma}\label{L4}
If $G$ is a $K_t$-saturated graph with $\delta(G) = t+1$, $\chi(G) \geq t+1$, and 
$v \in V(G)$ with $d(v) = \delta(G)$, then $N(v)$ contains at least five copies of $K_{t-2}$.
\end{lemma}
\proof
Assume $G$ is a $K_t$-saturated graph with $\delta(G) = t+1$ and $\chi(G) \geq t+1$.  
Let $v \in V(G)$ with $d(v) = \delta(G) = t+1$.  
Let $N(v) = \{v_1, v_2, . . . v_{t+1}\}$, $W = \{v\} \cup N(v)$ and $U = V(G) - W$.  
Then by Lemma ~\ref{L2}, $N(v)$ contains at least three copies of $K_{t-2}$.  


Case $1$: Supppose $N(v)$ contains exactly three copies of $K_{t-2}$.

Then we have one of the following three cases as in all other cases, 
$G$ is not $K_t$-saturated graph:

(a) $K_{t-2}^{(1)} \cong \langle v_1, v_2, . . . , v_{t-2} \rangle$, 
$K_{t-2}^{(2)} \cong \langle v_2, v_3, . . . , v_{t-1} \rangle$,
$K_{t-2}^{(3)} \cong \langle v_3, v_4, . . . , v_{t} \rangle$, and 
$v_iv_{t+1} \in E(G)$ for $i = 3, 4, . . . , t-2$. 

(b) $K_{t-2}^{(1)} \cong \langle v_1, v_2, . . . , v_{t-2} \rangle$, 
$K_{t-2}^{(2)} \cong \langle v_3, v_4, . . . , v_{t} \rangle$, 
$K_{t-2}^{(3)} \cong \langle v_4, v_5, . . . , v_{t+1} \rangle$, and 
$v_1v_{t+1} \in E(G)$.  

(c) $K_{t-2}^{(1)} \cong \langle v_1, v_2, . . . , v_{t-2} \rangle$, 
$K_{t-2}^{(2)} \cong \langle v_2, v_3, . . . , v_{t-1} \rangle$, 
$K_{t-2}^{(3)} \cong \langle v_2, v_3, . . . , v_{t-2}, v_{t} \rangle$, and 
$v_iv_{t+1} \in E(G)$ for $i = 3, 4, . . . , t-2$.  


In each case, define the following sets as in Figure 3.2:



\begin{eqnarray}
&& A = \{u \in U | uv_i \in E(G) \mbox{ for all } v_i \in V(K_{t-2}^{(1)})\} \mbox{ (green)}, \nonumber\\
&& B = \{u \in U | uv_i \in E(G) \mbox{ for all } v_i \in V(K_{t-2}^{(2)})\} \mbox{ (red)}, \nonumber\\
&& C = \{u \in U | uv_i \in E(G) \mbox{ for all } v_i \in V(K_{t-2}^{(3)})\} \mbox{ (blue)}, \nonumber\\
&& D = \{u \in U | uv_i \in E(G) \mbox{ for all } v_i \in N(v)\} \mbox{ (black)}. \nonumber
\end{eqnarray}


%$A = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(1)})\}$ (green), 
%$B = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(2)})\}$ (red), 
%$C = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(3)})\}$ (blue), and 
%$D = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in N(v)\}$ (black), as in Figure 2.


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


Furthermore, as seen earlier, $A \cup B$, $B \cup C$, and $A \cup C$ are 
complete bipartite graphs.  Now the graphs in Figure 2($a$) and 2($b$) 
are not $K_t$-saturated graphs as the addition of the edge $v_tv_{t+1}$ 
does not create a $K_t$.  Also, the graph in Figure 2($c$) is not a 
$K_t$-saturated graph as the addition of the edge $v_1v_{t+1}$ does 
not create a $K_t$.



Case $2$: Suppose $N(v)$ contains exactly four copies of $K_{t-2}$.

Then, as seen above, we have one of the following three cases as in all other cases, 
$G$ is not $K_t$-saturated graph:

(a) $K_{t-2}^{(1)} \cong \langle v_1, v_2, . . . , v_{t-2} \rangle$, 
$K_{t-2}^{(2)} \cong \langle v_2, v_3, . . . , v_{t-1} \rangle$,
$K_{t-2}^{(3)} \cong \langle v_3, v_4, . . . , v_{t} \rangle$, 
$K_{t-2}^{(4)} \cong \langle v_4, v_5, . . . , v_{t+1} \rangle$, and 
$v_1v_{t+1} \in E(G)$. 

(b) $K_{t-2}^{(1)} \cong \langle v_1, v_2, . . . , v_{t-2} \rangle$, 
$K_{t-2}^{(2)} \cong \langle v_2, v_3, . . . , v_{t-1} \rangle$,
$K_{t-2}^{(3)} \cong \langle v_3, v_4, . . . , v_{t} \rangle$, and 
$K_{t-2}^{(4)} \cong \langle v_3, v_4, . . . , v_{t-2}, v_{t}, v_{t+1} \rangle$.  

(c) $K_{t-2}^{(1)} \cong \langle v_1, v_2, . . . , v_{t-2} \rangle$, 
$K_{t-2}^{(2)} \cong \langle v_2, v_3, . . . , v_{t-1} \rangle$, 
$K_{t-2}^{(3)} \cong \langle v_2, v_3, . . . , v_{t-2}, v_{t} \rangle$, and 
$K_{t-2}^{(4)} \cong \langle v_2, v_3, . . . , v_{t-2}, v_{t+1} \rangle$.  


In each case, define the following sets as in Figure 3.3:


\begin{eqnarray}
&& A = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(1)})\} \mbox{ (green)}, \nonumber\\
&& B = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(2)})\} \mbox{ (red)}, \nonumber\\
&& C = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(3)})\} \mbox{ (blue)}, \nonumber\\
&& D = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(4)})\} \mbox{ (magenta)}, \nonumber\\
&& E = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in N(v)\} \mbox{ (black)}. \nonumber
\end{eqnarray}


%$A = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(1)})\}$ (green), 
%$B = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(2)})\}$ (red), 
%$C = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(3)})\}$ (blue), 
%$D = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(4)})\}$ (magenta), and 
%$E = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in N(v)\}$ (black), as in Figure 3.



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


Furthermore, as seen earlier, $A \cup B$, $B \cup C$, $C \cup D$, $A \cup C$, $A \cup D$, 
and $B \cup D$ are complete bipartite graphs.  Now the graph in Figure 3($a$) is not a 
$K_t$-saturated graph as the addition of the edge $v_1v_{t}$ does not create a $K_t$.  
Also, the graph in Figure 3($b$) is not a $K_t$-saturated graph as the addition of the 
edge $v_1v_{t+1}$ does not create a $K_t$.  Furthermore, $\chi(G) = t$ for the graph in 
Figure 3($c$), a contradiction as $\chi(G) \geq t+1$.

Hence, $N(v)$ must contain at least five copies of $K_{t-2}$.
\qed







\begin{lemma}\label{L5}
If $G$ is a $K_t$-saturated graph with $\delta(G) = t+1$, $\chi(G) \geq t+1$, and 
$n \geq t+4$, then $|E(G)| \geq (t-1)(n - \frac{t}{2}) - 2$.
\end{lemma}
\proof
Let $G$ be a $K_t$-saturated graph with $\delta(G) =t+1$, $\chi(G) \geq t+1$, and 
$n \geq t+4$.  Let $v \in V(G)$ such that $d(v) = \delta(G) = t+1$.  Then by 
Lemma ~\ref{L4}, $N(v)$ contains at least five copies of $K_{t-2}$.  Suppose $N(v)$ 
contains exactly five copies of $K_{t-2}$.  
Let $K_{t-2}^{(1)} \cong \langle v_1, v_2, . . . , v_{t-2} \rangle$, 
$K_{t-2}^{(2)} \cong \langle v_2, v_4, . . . , v_{t-2}, v_{t}, v_{t+1} \rangle$,
$K_{t-2}^{(3)} \cong \langle v_3, v_4, . . . , v_{t-2}, v_{t-1}, v_{t} \rangle$, 
$K_{t-2}^{(4)} \cong \langle v_4, v_5, . . . , v_{t+1} \rangle$, and 
\linebreak $K_{t-2}^{(5)} \cong \langle v_1, v_4, . . . , v_{t-2}, v_{t-1}, v_{t+1} \rangle$.  
Define the following sets as in Figure 3.4:


\begin{eqnarray}
&& A = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(1)})\} \mbox{ (brown)}, \nonumber\\
&& B = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(2)})\} \mbox{ (red)}, \nonumber\\
&& C = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(3)})\} \mbox{ (green)}, \nonumber\\
&& D = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(4)})\} \mbox{ (magenta)}, \nonumber\\
&& E = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(5)})\} \mbox{ (blue)}, \nonumber\\
&& F = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in N(v)\} \mbox{ (black)}. \nonumber
\end{eqnarray}


%$A = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(1)})\}$ (brown), 
%$B = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(2)})\}$ (red), 
%$C = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(3)})\}$ (green), 
%$D = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(4)})\}$ (magenta), 
%$E = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in V(K_{t-2}^{(5)})\}$ (blue), and 
%$F = \{u \in U | uv_i \in E(G) \mbox{ for } v_i \in N(v)\}$ (black), as in Figure 4.  


Then we obtain the graph as in Figure 3.4.

\smallskip 


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


It can be easily checked that any other forms of five copies of $K_{t-2}$ in $N(v)$ 
results in a graph that is not $K_{t}$-saturated.  Also, if there is an edge between 
two vertices of the sets $D$ and $E$, then $G$ is not $K_t$-saturated 
graph as we already have a $K_t$.  Furthermore, if one of the sets 
$A, B, C$ is empty and the number of vertices in the remaining two sets is 
exactly one, then vertices in the sets $D$ and $E$ fails to meet minimum 
degree condition.  If the either the set $D = \emptyset$ or $E = \emptyset$, 
but not both, then we do not have any problem.  So if either one of sets 
$A, B, C$ is empty or one of the sets $D, E$ is empty, but not both, then we 
have more vertices among the remaining sets or more vertices in the set $F$.  
In either case, degree of the vertices in these sets is at least $t+1$.  
Furthermore, if the set $F = \emptyset$, then we still have minimum number of 
edges, as the vertices are moved to either of the remaining sets with having 
same or higher degree.  Hence, we have the minimum number of edges if 
$|A| = |B| = |C| = |D| = |E| = 1$ and $|F| = n-t-7$, by convexity.  Hence, we have 


\begin{eqnarray*}
|E(G)| & = & t+1 + \left( \begin{array}{c} {t-5} \\ {2} \end{array} \right) + 3 + 3 
+ 6(t-5) + 6 + (t+1)(n-t-7)  \\ & &  + 5(t-2) + 9 \\ 
& = & \frac{(t-5)(t-6)}{2} + 4t + nt + n - t^2  - 25  \\ 
& = & n (t -1) - \frac{t(t-1)}{2} - 2 -2t + 2n - 8\\ 
& = & (t-1) (n - \frac{t}{2}) - 2 + 2n - 2t - 8 \\
& \geq & (t-1)(n - \frac{t}{2}) - 2
\end{eqnarray*}


\noindent as $n \geq t + 4$.  Now it can be easily checked that as we increase 
number of copies of $K_{t-2}$ in $N(v)$, then we increase number of edges.  
Hence, $|E(G)| \geq (t-1)(n - \frac{t}{2}) - 2$.
\qed







Now let's define $E(n, t, \delta)$ and $\chi(n, t, \delta)$.  $E(n, t, \delta)$ is defined to be the minimum number of edges that a graph with $n$ vertices and minimum degree $\delta$ can have if the addition of any edge creates a $K_t$.  Suppose $G$ is a graph on $n$ vertices with chromatic number $\chi(G) = t-1$ and minimum degree $\delta$.  Define $\chi(n, t, \delta)$ to be the minimum number of edges that $G$ can have such that the addition of any edge to $G$ increases the chromatic number.  The following Theorem is shown by Duffus and Hanson in \cite{dh86}.  


\begin{theorem}\label{DHtheorem}
For integers $n, t$, and $\delta$ where $2 \leq t \leq n$ and \newline $t-2 \leq \delta \leq \frac{t-2}{t-1}n$,

\begin{center}
$\frac{\delta + t - 2}{2}(n - \delta - 1) + \delta + \left( \begin{array}{c} {t-2} \\ {2} \end{array} \right) \leq E(n, t, \delta) \leq \chi(n, t, \delta)$.
\end{center}
\end{theorem}


Now applying the above theorem to a $K_t$-saturated graph $G$ with $\chi(G) \geq t+1$, we obtain the following result.







\begin{lemma}\label{L6}
If $G$ is a $K_t$-saturated graph,  $\delta(G) \geq t+2$, $\chi(G) \geq t+1$, and $n \geq 5t - 7$, then $|E(G)| \geq (t-1)(n - \frac{t}{2}) - 2$.
\end{lemma}
\proof
Let $G$ be a $K_t$-saturated graph with $\delta(G) \geq t+2$, $\chi(G) \geq t+1$, and $n \geq 5t - 7$.  Applying the above Theorem, Theorem ~\ref{DHtheorem}, with given parameters, we obtain the following:


\begin{eqnarray*}
|E(G)| & \geq & \frac{t+2+t-2}{2} (n-t-2-1) + t+2 + \left( \begin{array}{c} {t-2} \\ {2} \end{array} \right) \\ 
& = & (t-1) (n - \frac{t}{2}) - 2 + n - 5t + 7 \\
& \geq & (t-1)(n - \frac{t}{2}) - 2
\end{eqnarray*}


\noindent as $n \geq 5t - 7$.  
\qed







\begin{theorem}\label{LB3}
If $G$ is a $K_t$-saturated graph,  $\delta(G) \geq t$, $\chi(G) \geq t+1$, and $n \geq 5t-7$, 
then $|E(G)| \geq (t-1)(n - \frac{t}{2}) - 2$.
\end{theorem}
\proof
Proof follows from Lemma ~\ref{L3}, Lemma ~\ref{L5}, and Lemma ~\ref{L6}.
\qed






\begin{theorem}\label{LB}
If $G$ is a $K_t$-saturated graph of order $n \geq 5t-7$ and $G$ is not isomorphic to 
$K_{t-2} + \overline{K_{n-t+2}}$, then $E(G) \geq (t-1)(n - \frac{t}{2}) - 2$.
\end{theorem}
\proof
Proof follows from Theorem ~\ref{LB1}, Theorem ~\ref{LB2}, and Theorem ~\ref{LB3}.
\qed







\section{Upper Bound for $K_{t}$-saturated Graphs}
\label{sec:UpperBoundfor$K_{t}$-saturatedGraphs}



% In  \cite{ht91}, Hanson and Toft gave the following construction.  The graphs in the family
% $\mathcal{T}_n^k$ are on $n$ vertices consisting of a complete $(k-1)$-partite graph on $n-2$
% vertices, with classes of independent points $C_1, C_2, . . . , C_{k-1}$, together with two adjacent vertices $x$ and $y$ and where each vertex of $C_1$ is joined to precisely one of $x$%  or $y$, $x$ and $y$ are each  adjacent to at least one vertex of $C_1$, no vertex of $C_2$ is adjacent to either $x$ or $y$ and all vertices of $C_i$, $i > 2$ are adjacent to both $x$ and $y$.  For $k \geq 3$, define $T'_{k-1,n}$ to be graphs in $\mathcal{T}_n^k$ for which $|C_1|% +1, |C_2|+2, |C_3|, . . . , |C_{k-1}|$ are equal or as equal as possible.  For $n \geq 3k-4$ % we can describe $T'_{k-1, n}$ as follows: let $n+1 = t(k-1)+r$, $0 \leq r < k-1$ and let $G$ % denote a member of $\mathcal{T}_{n_0}^k$ on $n_0 = n-r$ vertices and $e_0 = e(T_{k-1,n-r}) - % (t-2)$ edges where the classes $C_i$ satisfy $|C_1| = t-1, |C_2| = t-2$ and $|C_i| = t$, $i> % 2 $ ($G$ is unique up to adjacencies of $x$ and $y$ to class $C_1$).  Define $T'_{k-1,n}$ to % be a graph $G$ with one vertex added to precisely $r$ of the classes $C_1, . . . , C_{k-1}$.  % Note that the graphs $T'_{k-1,n}$ are maximal, with respect to the number of edges, in the family $\mathcal{T}_n^k$.  Then they show the following result. 


% \begin{theorem}\label{thmHT}
% Let $G$ be a maximal $K_{k}$-saturated graph on $n \geq k+2 \geq 5$ vertices with $\chi(G) \geq k$, then $G$ is a $T'_{k-1,n}$ graph.
% \end{theorem}



From Theorem ~\ref{thmHT} by Hanson and Toft \cite{ht91}, we have the following result.



\begin{theorem} \label{UB}
If $G$ is not a complete $(t-1)$-partite $K_t$-saturated graph for $t \geq 5$, then $E(G) \leq \lfloor \frac{(t-2)n^2 - 2n + (t-2)}{2(t-1)} \rfloor + 1$.
\end{theorem}
\proof
Let $G$ be a $K_t$-saturated graph of order $n$.  Suppose $G$ is not a complete $(t-1)$-partite graph.
Since $G$ is not $(t-1)$-partite, $\chi(G) \geq t$.  Hence, by Theorem~\ref{thmHT}, 
$|E(G)| \leq |E(T'_{t-1, n})|$.  Let $n+1 = (t-1)s + r$, $0 \leq r < t-1$.  We will consider two
cases.  One with $r = t-2$ and another with $0 \leq r \leq t-3$.  For the first case, a straightforward computation shows, \linebreak $|E(T'_{t-1, n})| = \frac{(t-2)n^2 - 2n (3-2t) - 4t^2 + 16t -12}{2(t-1)} + 1 < F(n, t)$.  Now for
$0 \leq r \leq t-3$, 


\begin{eqnarray*}
|E(T'_{t-1, n})| & = & \frac{(t-r-3)(t-r-4)}{2}s^2 + \frac{r(r-1)}{2}(s+1)^2 +  \\ & & 
rs(s+1)(t-r-3) + (s-1)(s-2) + r(s-1)(s+1)  \\ & & + (t-3-r)(s-1)s + r(s-2)(s+1) + (t-3-r)(s-2)s  \\ & & + 1 + s-1+2r(s+1) + 2(t-3-r)s \\ & = & \frac{(t-2) n^2 -2n + t-2 - tr + r + r^2}{2(t-1)} + 1. \\
\end{eqnarray*}
  

Hence, it is easy to see that the number of edges is maximum when $r=0$.  So $|E(T'_{t-1, n})| =
\frac{(t-2)n^2-2n+(t-2)}{2(t-1)} + 1$.    
\qed







\section{Edge Spectrum of $K_{t}$-saturated Graphs}
\label{sec:EdgeSpectrumof$K_{t}$-saturatedGraphs}




\begin{theorem} \label{Main}
Let $n \geq 5t-7$ and $m$ be nonnegative integers.  There is an $(n, m)$ $K_t$-saturated graph $G$ if and only if $G$ is a 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$.
\end{theorem}
\proof
Let $n \geq 5t-7$ and $m$ be nonnegative integers.  Let $G$ be  an $(n, m)$ $K_t$-saturated graph.  If $G$ is a $(t-1)$-partite graph, then $G$ must be a complete $(t-1)$-partite graph, otherwise an edge may be added without creating a $K_t$.

Assume $G$ is not a complete $(t-1)$-partite graph.  Then from Theorem ~\ref{LB} and Theorem ~\ref{UB}, $(t-1)(n - \frac{t}{2}) - 2 \leq m \leq \lfloor \frac{(t-2)n^2 - 2n + (t-2)}{2(t-1)} \rfloor + 1$.

It is sufficient to construct an $(n, m)$ $K_t$-saturated graph for each value of $m$.  If $m = (t-2)(n - \frac{t-1}{2})$, then $G \cong K_{t-2} + \overline{K_{n-t+2}}$.  If $G$ is a complete $(t-1)$-partite graph, then $G$ is a $K_t$-saturated graph.

Now to show the existence of a $K_t$-saturated graph for $(t-1)(n - \frac{t}{2}) - 2 \leq m \leq \lfloor \frac{(t-2)n^2 - 2n + (t-2)}{2(t-1)} \rfloor + 1$, we use mathematical induction.  We know the statement is true for $t = 3, 4$.  Assume the statement is true for $t-1$.  Let $(t-1)(n - \frac{t}{2}) - 2 \leq m \leq \lfloor \frac{(t-2)n^2 - 2n + (t-2)}{2(t-1)} \rfloor + 1$.  We want to construct a $K_t$-saturated graph for each value of $m$.  Let $G \cong H + \overline{K_q}$, where $H$ is a $K_{t-1}$-saturated graph of order $n-q$.  Then by the induction hypothesis, $(t-2)(n - q - \frac{t-1}{2}) - 2 \leq |E(H)| \leq \lfloor \frac{(t-3)(n - q)^2 - 2(n - q) + (t-3)}{2(t-2)} \rfloor + 1$.  Hence, $(t-2)(n - q - \frac{t-1}{2}) - 2 + (n - q)q \leq |E(G)| \leq \lfloor \frac{(t-3)(n - q)^2 - 2(n - q) + (t-3)}{2(t-2)} \rfloor + 1 + (n - q)q$.  For $q =1$, $(t-1)(n-\frac{t}{2})-2 \leq |(E(G)| \leq \lfloor \frac{(t-3)(n - 1)^2 + 2 (t-3)(n - 1) + (t-3)}{2(t-2)} \rfloor + 1$, for $q=2$, $t(n-\frac{t}{2})-\frac{t}{2} - 3 \leq |(E(G)| \leq \lfloor \frac{(t-3)(n - 2)^2 + 2 (2t-5)(n - 2) + (t-3)}{2(t-2)} \rfloor + 1$, and so on.  Again, it can be easily seen that these intervals overlap.  Furthermore, we obtain the lower bound when $q=1$, $(t-1)(n-\frac{t}{2})-2$.  Now let $f(q)= \lfloor \frac{(t-3)(n - q)^2 - 2(n - q) + (t-3)}{2(t-2)} \rfloor + 1 + (n - q)q$.  Then $f(q)$ is maximum when $q = \frac{n+1}{t-1}$ and $f(\frac{n+1}{t-1})= \lfloor \frac{(t-2)n^2 - 2n + (t-2)}{2(t-1)} \rfloor + 1$
\qed



