\chapter{Construction of Minimal Complete Graphs}\label{chap4}
 
 Using search space reductions described in Section~\ref{sec:ssr} and the Star Analysis 
 technique outlined in Section~\ref{sec:dtpl}, an effective algorithm has been developed
 for building those minimal K$_{n}$ derivable from one minimal K$_{n-1}$.  This chapter describes
 a system that iteratively builds all minimal K$_{n}$ from all minimal K$_{n-1}$, making use of
 only a subset of minimal K$_{n}$.
 Section~\ref{sec:ifkn} discusses the use of graph isomorphism to reduce the number of minimal
 K$_{n-1}$ graphs that need to be used as root graphs in the growth process.  An overview of the
 entire inductive process is covered in Section~\ref{sec:gmfm}.
     
 \section{Isomorphic Families of Minimal K$_{n}$}\label{sec:ifkn}
 
 If two graphs are isomorphic (refer to Definition~\ref{def:iso}) they differ only by the labeling
 of their vertices and possibly the physical view chosen for representation.  The defining 
 characteristics, or mathematical structures, of the graphs are identical.  In the process 
 of generating minimal K$_{n}$ from minimal
 K$_{n-1}$, it is not necessary to use all minimal K$_{n-1}$ graphs as root graphs. Only a 
 single representative is needed from each isomorphic family, composed of all graphs that are 
 isomorphic.  
 
 It is imperative to categorize graphs of order $n$ into isomorphic families to be able to
 select the minimum number of necessary representatives to use as root graphs for the next
 iteration of minimal graph derivation.  The software product {\it nauty}, written by
 Brendan McKay~\cite{m81:pgi}, is employed for isomorphism testing. A C program was written
 to call {\it nauty} for building sets of isomorphic families. {\it nauty} compares two graphs 
 and notifies the calling program if they are isomorphic or not.  
 Each new graph in the list to be tested is compared to a current family representative and 
 added to that family if it fits, otherwise a new family is created.  After testing of all graphs,
 a set of root graphs 
 is compiled by selecting one representative from each isomorphic family.  
 
 Graphs of order $n \le 4$ all have one isomorphic family.
 Table~\ref{tbl:isofamilies} lists the number of isomorphic families of minimal 
 K$_{n}$ for $5 \le n \le 11$.
      
  	        
  \begin{table}[h]
	\centering
		\begin{tabular}{|c|cccccc|} \hline
	$n$ 		         &  5 & 6 &  7 &  8 &    9 &    10   \\ \hline
	Graphs generated & 12 & 4 & 76 & 20 & 4,560 & 56,618  \\ \hline
	Iso families     &  1 & 1 &  5 & 3  & 1,453 &  5,679  \\ \hline
		\end{tabular}
	\caption{Isomorphic Families of Minimal K$_{n}$}
	\label{tbl:isofamilies}
\end{table}   
 
 The need for exploiting isomorphic graphs is evident by examination of Table~\ref{tbl:isofamilies}.
 For example, for $n = 9$, 4560 graphs were generated from minimal K$_{8}$ using
 Radical Region Restriction.  The number of non-isomorphic graphs necessary 
 for iteration to minimal K$_{10}$ was 1453, a reduction of sixty-eight percent.  
 
 Further algorithmic exploitation of the topological structure of the root graphs such as
 symmetry, local and global, or region neighborhood analysis may allow
 for reduction of the current requirement that all regions of the root graph be
 used for new vertex placement.  Refer to Chapter~\ref{chap5} for more discussion of this
 topic.     
 
 \section{Growing Minimal K$_{n}$ from Minimal K$_{n-1}$}\label{sec:gmfm}
 
 Minimal K$_{4}$ was used as the initial starting point in growing minimal K$_{n}$ inductively 
 from minimal K$_{n-1}$.  Minimal K$_{4}$ is a plane graph with no crossings, and there is only 
 one minimal K$_{4}$ up to isomorphism.  Figure~\ref{fig:K4} illustrates one labeling of the initial graph
 used to grow minimal K$_{5}$ with its associated region list representation.  A region list 
 is just one way a graph can be represented.  
 Using Figure~\ref{fig:K4} think of
 standing inside region R1.  Begin at vertex 1 with your left hand on edge (1,2).  Walk around 
 R1 keeping your left hand
 on the boundary of R1, and you will trace the region description for R1: 1, 2, 4.  Vertex 1 is adjacent
 to vertex 2 is adjacent to vertex 4 is adjacent to vertex 1. All regions of the graph are described
 in this fashion.    
   
 \begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=4.5in]{ch4/K4chap4.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{K$_{4}$ and its Region List Representation}
       \label{fig:K4}
 \end{figure}
 
	Using minimal K$_{4}$ as the example, the entire process of generating the isomorphic family 
	representatives of minimal K$_{5}$ necessary to generate minimal K$_{6}$ is illustrated in the
	following steps. 
		
	Step 1:	 Minimal K$_{4}$, the feeder graph, represented as a region list, is presented to
	the Input Generator.  The Input Generator adds to the region list a list of edges to add
	to the graph necessary to construct minimal K$_{5}$. Each region in K$_{4}$ is used
	as an initial placement location for vertex 5.  Thus 4 different configurations are presented
	to the Star Analysis module.  Figure~\ref{fig:K4PlusV5} illustrates these four initial
	configurations.
		  
 \begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=4.5in]{ch4/K4PlusV5chap4.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{K$_{4}$ with Vertex 5 Placement and Edges to Add}
       \label{fig:K4PlusV5}
 \end{figure}  
	
	Step 2:	For each of the four configurations in Figure~\ref{fig:K4PlusV5}, the Star
	Analysis Module is instantiated.  The resulting Distance Tree and Path List for the configuration
	placing vertex 5 in R1 is illustrated in Figure~\ref{fig:K5dtpl}.
	
\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=4.5in]{ch4/K5dtplChap4.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Star Analysis: K$_{4}$ (with Vertex 5 in Region 1) to K$_{5}$}
       \label{fig:K5dtpl}
 \end{figure}  	
 
 In moving from Figure~\ref{fig:K4PlusV5} to Figure~\ref{fig:K5dtpl}, notice that the edges
 to add, (5,1), (5,2), and (5,4), are all direct connections from within region R1.  They
 are not included in the Distance Tree because they will not produce any crossings in the final
 graph descriptions.  To place edge (5,3), there are three distinct regions sharing boundary edges with 
 region R1: R2 {\it via} edge (2,4), R3 {\it via} edge (1,4) and R4 {\it via} edge (1,2).  The Distance Tree
 reflects these three paths.  From each of these three regions there is a direct connection
 to vertex 3. Thus, there are three distinct paths with one crossing 
 each from region R1 to vertex 3.  Each path is reflected in the Distance Tree.  From the
 Distance Tree it is determined that exactly one crossing is required in growing the initial
 configuration, minimal K$_{4}$ with vertex 5 in region R1, to a K$_{5}$.  No more than (in
 this case exactly) three graphs will achieve this conclusion.  
 
 The Path List reflects all paths from vertex 5 in region R1 to each of the four vertices to which
 it must connect.  The directly connected vertices are included here as well as all possible
 shortest paths to other vertices (only vertex 3 for this example).
 
 Step 3: Selection of graphs for construction follows the Path List generation.  For the
example of K$_{4}$ to minimal K$_{5}$, recall from Figure~\ref{fig:K4PlusV5} that
there are 4 configurations to examine.  Each of these configurations generates
a Distance Tree and Path List that is similar to the one shown in 
Figure~\ref{fig:K5dtpl}, each representing one crossing and
three graphs to achieve minimal K$_{5}$.  So four Path List files are created,
each with minimal K$_{5}$ (one crossing) from minimal K$_{4}$ descriptions.  In
this case all Path Lists represent minimal K$_{5}$, so all Path List files are
examined for construction of minimal K$_{5}$.  Twelve graph descriptions
will be created (three from each path list), each representing a minimal
K$_{5}$.  The graph description construction process lays down all K$_{n-1}$ star graphs
centered at vertex $n$ created from the Path List description into the appropriate 
minimal K$_{n-1}$.  The process splits regions as edge segments are placed and the star 
edges are laid down from each $n-i$, $1 \le i \le n-1$, vertex to vertex $n$.

In the general case of constructing minimal K$_{n}$ from minimal K$_{n-1}$,
it is common for $n$ even for the Star Analysis Module to locate an 
assortment of crossings, thus generating locally minimal K$_{n}$ based on
the region in which vertex $n$ is placed.  For example, Figure~\ref{fig:K7}
shows a minimal K$_{7}$ with four regions labeled.  
	
\begin{figure}[!ht]
       \begin{center}
          \includegraphics[width=3in]{ch4/K7Chap4.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{A Minimal K$_{7}$}
       \label{fig:K7}
 \end{figure}  	
A portion of the Path Lists 
generated for K$_{8}$ created from the K$_{7}$ of Figure~\ref{fig:K7} is shown in Figure~\ref{fig:K8pathlists}.  The file extension
following the underscore is interpreted as: {\it isomorphic family.region number.crossings}.
This listing indicates that Vertex 8 placement
in region 10 leads to generation of locally minimal K$_{8}$ with 19 crossings.
Vertex 8 placement in region 11 leads to minimal K$_{8}$ with 20
crossings, {\it etc}.  In the search for minimal K$_{8}$, graph generation is
performed on those Path List files that indicate globally minimal K$_{8}$, 
or 18 crossings, constructed by placing the new vertex in region 12 in Figure~\ref{fig:K7}. 
	
\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=3.0in]{ch4/K8PathlistsChap4.pdf}
         	
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Path Lists with Locally Minimal K$_{8}$}
       \label{fig:K8pathlists}
 \end{figure}  	
In general, minimal K$_{n}$ will be found by examining
those Path Lists that represent min(min K$_{n}$ for region $i$ in initial graph $j$), 
$1 \le i \le r$, 
where $r$ is the number of regions in the initial root graph(s). 
This is a substantial savings over the search space reduction techniques
of Section~\ref{sec:ssr}.  In those cases, energy was expended growing all
graphs until they exceeded the current minimum value found.  When a graph
exceeded the current minimum it was discarded.  Not only was energy spent
growing a locally minimum graph, but the graph was discarded prior to completion so
it was not available for future analysis of the underlying structure of those
nonminimal graphs.

To date, for $n$ odd, $5 \le n \le 9$, all Path Lists represent minimal
graphs.  This means that vertex $n$ placement in any region of K$_{n-1}$, for $n$ odd, 
generates at least one globally minimal K$_{n}$.  This phenomenon is 
discussed further in Chapter~\ref{chap5}.  

Returning to the example of preparing minimal K$_{5}$ for generating
minimal K$_{6}$, four Path List descriptions of K$_{5}$, with a
total of twelve graph descriptions among them, are ready for building.

Step 4:	Generation of graph descriptions is, as stated above, a selective
process based on the interest in minimal graphs or locally minimal graphs.
In this example, all K$_{5}$ Path Lists indicate minimal graphs, so
all are evaluated, and twelve minimal K$_{5}$ graph descriptions are constructed.

Step 5: A format conversion is required for isomorphic testing. {\it nauty} 
requires that graphs be represented as adjacency matrices.  
Figure~\ref{fig:RegListAdjMat} illustrates both region list and adjacency matrix 
for minimal K$_{5}$.  Notice that the adjacency matrix has
a 1 for each (row, column) vertex pair that is adjacent in the region list,
otherwise the entry is a 0.  

	
\begin{figure}[!ht]
       \begin{center}
				 \includegraphics[width=4.0in]{ch4/RegListAdjMatChap4.pdf}        	
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{K$_{5}$ Region List and Associated Adjacency Matrix}
       \label{fig:RegListAdjMat}
 \end{figure}  	

Step 6:  Isomorphic testing is performed on all minimal K$_{5}$ graphs. 
Isomorphism testing generates a
listing of all the isomorphic families for the graphs tested and  enumerates 
all the members in each family.  Figure~\ref{fig:K5Iso} shows the 
isomorphic testing results for the twelve minimal K$_{5}$ graphs tested.  
Notice that in the case of minimal K$_{5}$ there is only one isomorphic
family, so only one representative is necessary for moving ahead to grow minimal K$_{6}$.  

	
\begin{figure}[!t]
       \begin{center}
           \includegraphics[width=3.5in]{ch4/K5IsoChap4.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Isomorphic Test Results on K$_{5}$}
       \label{fig:K5Iso}
 \end{figure}  	

Actually, all four initial K$_{4}$ configurations are
isomorphic, and all regions of K$_{4}$ are isomorphic.  Thus, placement
of vertex 5 in any region in any configuration will always generate a
graph description isomorphic to any other placement.  This represents further
analysis that may be performed at the Step 1 - Step 2 interface to see
if algorithmic topological structure analysis of the graphs being processed may  be
exploited to result
in the testing of fewer regions.  See Chapter~\ref{chap5} for more discussion on this. 

Step 7:  Isomorphic family representative selection is performed to extract
one representative from each isomorphic family from minimal K$_{n}$ to use as a
feeder graph in generating minimal K$_{n+1}$.  The representative index is determined
from the isomorphic testing results and the associated graph description
(region list) is extracted from the graph descriptions generated in Step 4.
All the isomorphic family representative graph descriptions are consolidated into 
one file for ease of handling, and the process begins again at Step 1 using 
minimal K$_{n}$ to step up to minimal K$_{n+1}$.

In summary, Figure~\ref{fig:process} illustrates the seven-step process just outlined.

	
\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=3.5in]{ch4/ProcessChap4.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Iterative Process to Grow Minimal K$_{n}$}
       \label{fig:process}
 \end{figure}  	
It is noted that at no step in this process does the system know that
it is working on complete graphs.  The only defining factor indicating
complete graphs is the initial feeder graphs used along with the list of
edges to add.  Thus, it is anticipated that this process will
seamlessly allow for examination of other graph families with no modification
other than the initial graph description(s) and the list of edges to add.  
A specific example of complete bipartite graph growth from K$_{2,3}$ to 
K$_{3,3}$ and K$_{2,4}$ is presented in Chapter~\ref{chap5}.



   

      
 
 
  
 
 