\documentclass[pdftex,12pt]{article}
\usepackage{e-jc}
% Please remove all other commands that change parameters such as
% margins or pagesizes.
% only use standard LaTeX packages
% only include packages that you actually need
% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}
% we recommend the graphicx package for importing figures
\usepackage{graphicx}
% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins
% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem*{theorem*}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\newtheorem*{theorem-nolabel}{Theorem}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
%%%%%%%%%% OWN PACKAGES REQUIRED
\usepackage{booktabs} % Layout of tables
\usepackage[table]{xcolor} % To color cells in tables
\usepackage{natbib}
\usepackage{tikz}
\usepackage{array}
\newcolumntype{L}[1]{>{\raggedright\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\newcolumntype{R}[1]{>{\raggedleft\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% if needed include a line break (\\) at an appropriate place in the title
\title{Applications of integer programming methods to cages}
% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address
\author{Frans J.C.T. de Ruiter\thanks{Part of this author's work was done while he studied for the degree of M.Sc. in Applicable Mathematics at the Department of Mathematics, London School of Economics and Political Science.}\\
\small Department of Econometrics and Operations Research\\[-0.8ex]
\small Tilburg University\\[-0.8ex]
\small Tilburg, The Netherlands.\\
\small\tt f.j.c.t.deruiter@tilburguniversity.edu\\
\and
Norman L. Biggs\\
\small Department of Mathematics\\[-0.8ex]
\small London School of Economics and Political Science\\[-0.8ex]
\small London, U.K.\\
\small\tt n.l.biggs@lse.ac.uk
}
%v \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}
\date{\dateline{November 25, 2014}{ }\\
\small Mathematics Subject Classifications: 05C25, 05C35}%05-04, 90C10, 90C90, 68R05, 68R10}
\begin{document}
\maketitle
% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..." or "we show that...". Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.
\begin{abstract}
The aim of this paper is to construct new small regular graphs with girth $7$ using integer programming techniques. Over the last two decades solvers for integer programs have become more and more powerful and have proven to be a useful aid for many hard combinatorial problems. Despite successes in many related fields, these optimisation tools have so far been absent in the quest for small regular graphs with a given girth. Here we illustrate the power of these solvers as an aid to construct small regular girth $7$ graphs from girth $8$ cages.
% keywords are optional
\bigskip\noindent \textbf{Keywords:} Integer programming applications; cage problem
\end{abstract}
\section{Introduction}
The \emph{girth} of a graph is the length of its shortest cycle. For the cage problem one aims to construct regular graphs of degree $k$ with minimum number of vertices required to have girth $g$. It is known that a regular graph with degree $k$ and girth $g$ can be created for any $k\geq 2$ and $g\geq 3$ \cite{ErdosSachs1963}. The real challenge is to find a regular graph with the least number of vertices which still has girth $g$. The graphs that are of minimum order for degree $k$ and girth $g$ are referred to as $(k,g)$-\emph{cages}. Often, the constructions are not known to be cages and the resulting $(k,g)$-graphs only provide upper bounds, which we call \emph{record graphs}. For an overview of the known cages, record graphs and their constructions see the up-to-date dynamic cage survey \cite{ExooJaycay2013}. Only little appears to be known for the girth $7$ case. In this paper we construct new record graphs with girth $7$, improving the upper bounds for regular girth $7$-graphs with degrees up to $14$. This is achieved by a novel approach that uses the power of modern linear programming solvers and combinatoric properties of some known girth $8$ graphs.\\
\\
The only known cages with girth $7$ are the McGee graph \cite{McGee1960} of order $24$ and the more recently discovered $(4,7)$-cage of order $67$ \cite{ExooJaycay2013,Exooetal2011}. For all other degrees and girths only record graphs, which give an upper bound on the order of the cages, are known. This paper contributes to the girth $7$ case of the cage problem by showing how to use integer programming techniques to construct record graphs with girth $7$ for degrees up to $14$. Table \ref{tab:newrecords} lists the order of our new record graphs, as well as the previous best-known record graphs.\footnote{The adjacency lists of all these graphs, including the known girth $8$ record graphs, are available online at \url{https://github.com/FransdR/Record-graphs-girth-7-and-8.git}}
\begin{table}[h!]
\centering
\caption{Our new constructed graphs compared to old record graphs.}
\begin{tabular}{|r|r|r|l|}
\toprule
Degree & New & Old & Old record due to\\
$k$ & record & record & \\
\midrule
7 & $632$ & $640$ & Exoo \cite{ExooPersonalCommunication}\\
8 & $777$ & $799$ & Sauer \cite{Sauer1967} \\
9 & $1104$ & $1152$ & Araujo-Pardo \cite{AraujoPardo2010}\\
10 & $1611$ & $1639$ & Sauer \cite{Sauer1967} \\
11 & $2576$ & $2596$ & Araujo-Pardo \cite{AraujoPardo2010}\\
12 & $2893$ & $2927$ & Sauer \cite{Sauer1967} \\
13 & $4292$ & $4316$ & Araujo-Pardo \cite{AraujoPardo2010} \\
14 & $4719$ & $4759$ & Sauer \cite{Sauer1967} \\
\bottomrule
\end{tabular}%
\label{tab:newrecords}%
\end{table}%
\section{The excision method}\label{sec:Excision}
In this section we show how to construct regular graphs with girth $g-1$ from regular graphs with girth $g$ by \emph{excision}. In an excision operation one first removes vertices and their adjacent edges from a graph with degree $k$ and girth $g$. In the second step one has to join the remaining vertices with each other to obtain a regular graph of degree $k$ and girth $g-1$. We give results for the size of the set of vertices that can be removed to end up with a regular graph with girth $g-1$. For joining up the vertices again, we use integer programming methods. For girth $7$ there is a rather standard result that ensures us that for odd $k$ we can remove $2k$ vertices from a $k-$regular graph with girth $8$. The proof for odd $k$ and even girth $g$ is given in \cite{AraujoPardo2010}. Another proof can be based on the excision proof for the cubic situation \cite{Biggs1998}. Typical for those proofs is that the excised set of vertices and edges form a tree and the diameter of the tree is $3$. An example of such a tree for degree $5$ and girth $7$ is given in Figure \ref{fig:ExcisionForGirth7}.
\begin{figure}[h!]
\centering
\begin{tikzpicture}
[scale=.8,auto=left,every node/.style={radius=10pt,circle,inner sep = 1.5pt,fill=black!100}]
\node (u) at (5,3.5) {};
\node (v) at (7,3.5) {};
\draw (u) -- (v);
\foreach \x in {0,1,...,3} {
\node (u\x) at (3,\x+2) {};
\node (v\x) at (9,\x+2) {};
}
\foreach \x in {0,1,...,3} {
\draw (u) -- (u\x);
\draw (v) -- (v\x);
\foreach \y in {0,1,...,3} {
\draw[black!50] (u\x) -- (2,\x+1.75 + \y/5);
\draw[black!50] (v\x) -- (10,\x+1.75 + \y/5);
}
}
\end{tikzpicture}
\caption{Subtree consisting of $10$ vertices that can be removed from a $(5,8)$-graph to obtain a $(5,7)$-graph.}\label{fig:ExcisionForGirth7}
\end{figure}
Joining up the vertices to obtain a regular graph of degree $k$ can be done in an arbitrary way, as long as the joined vertices shared a common neighbour in the excised tree. An example that can be obtained in this way is the McGee graph ($k=3$) \cite{McGee1960}. For the girth $7$ case with higher degrees ($k\geq4$) we might be able to excise a graph that consists of more than $2k$ vertices. Examples where this is successful are the cases $k=5$ and $k=6$ \cite{McKayYuanshen}. It is possible to excise $18$ vertices in both cases. In the following sections we show how integer programming methods can be used to successfully excise larger sets of vertices for degrees $7$ up to $14$. We first describe the set of excised vertices and integer programming methods we developed for odd degrees $7,9,11$ and $13$ and after then a similar method for even degrees $8,10,12$ and $14$. Throughout this paper we denote $V$ as the set of vertices in the original graph, $S$ the set of vertices we are going to excise and $V\backslash S$ the vertices that remain after excision.
\section{Odd degree graphs}\label{subsec:ExcisionIndividual}
For odd degree graphs we are going to excise a tree that has diameter $4$, instead of a tree with diameter $3$ as was done in the more general results \cite{AraujoPardo2010}. Let us first explain why we can not join the edges from two neighbours in an arbitrary way if the diameter of $S$ is 4. Consider two vertices $u$ and $v$ that are at distance $4$ in $S$. Let $\{u_1,\dots,u_{k-1}\}$ and $\{v_1,\dots,v_{k-1}\}$ be the neighbours of respectively $u$ and $v$ that are still in $V-S$ and therefore have degree $k-1$. There is path of length $6$ going through $S$ from any $u_i$ to any other $v_j$. Hence, there could be a path through $V \backslash S$ of length $2$ from $u_i$ to $v_j$. Let $d(x,y)$ denote the distance between vertex $x$ and $y$ only using nodes from $V \backslash S$. If $d(u_1,v_1) + d(u_2,v_2) = 4$, then we are not allowed to add both edges $\{u_1,u_2\}$ and $\{v_1,v_2\}$ in the excision operation because that would create a $6$-cycle. If this is the case, we call $(\{u_1,u_2\},\{v_1,v_2\})$ a \emph{forbidden combination}. Let $\bar E$ be the pairs of vertices $\{x,y\}$ such that both $x$ and $y$ have degree $k-1$. We have to choose edges from $\bar E$ to create a regular graph of degree $k$. The set $R \subset \bar E \times \bar E$ that contains all forbidden combination of edges is given by
\begin{align}
\resizebox{0.92\hsize}{!}{$R = \Bigl\{\left(\{x,y\},\{w,z\}\right) \in \bar E \times \bar E\ |\ d(x,w) + d(y,z) = 4 \text{ or } d(x,z)+d(w,y) = 4\Bigr\}$. }\label{eq:forbiddencombinations}
\end{align}
The set $R$ only consists of pairs of edges, so we did not include any forbidden triples, quadruples etc. We do not have to mark any combinations of three of more edges as forbidden because every path through vertices from $V \backslash S$ joining $u_i$ and $v_j$ has length at least $2$. Hence, a cycle with three or more `new' edges from $\bar E$ has length at least $2+2+2+1+1+1 = 9$.\\
\\
We use the set of forbidden combination of edges $R$ to determine whether we can join edges after excising the subtree $S$ to obtain another regular graph of degree $k$. Excision of $S$ is successful if we can determine an edge set $X \subset \bar E$ such that:
\begin{enumerate}
\item[(i)] After adding edges from $X$, the degree of every vertex is $k$.
\item[(ii)] For every edge pair $(e,f) \in R$, at most one of the edges $e$ or $f$ is in $X$.
\end{enumerate}
To model these conditions we introduce decision variables $x_e$ for all $\bar E$ to decide whether or not to include an edge $e \in \bar E$:
\begin{align*}
x_e = \begin{cases} 1 & \text{ if } e \in X\\ 0 & \text{ if } e \not \in X.\end{cases}
\end{align*}
Using these decision variables, we can now translate the degree condition (i) into
\begin{align*}
\sum_{e\in \delta(u) \cap \bar E}x_e = 1 & \qquad \forall u \in N(S)\backslash S,
\end{align*}
where $\delta(u)$ is the set of edges incident with vertex $u$ and $N(S)\backslash S$ being the set of vertices that have a neighbour in $S$, but are not in $S$ themselves. Note that the degree of every vertex in $N(S)\backslash S$ is equal to $k-1$ before adding edges. So when every one of those vertices is adjacent to exactly one new edge from $\bar E$, condition (i) is satisfied. The second condition can be modelled as
\begin{align}
x_e + x_f \leq 1 & \qquad \forall (e,f) \in R. \label{eq:constraint_forbiddencombi}
\end{align}
Hence, the resulting integer programming model is
\begin{align}
\begin{aligned}
& {\text{max}}
& & 1\\
& \text{such that}
& & \sum_{e\in \delta(u) \cap \bar E}x_e = 1 \qquad \forall u \in N(S)\backslash S\\
& & &x_e + x_f \leq 1 \qquad \forall (e,f) \in R.
\end{aligned}
\tag{Excision-ILP}\label{program:individualexcision}
\end{align}
We have used program \eqref{program:individualexcision} for odd degrees $3 \leq k \leq 13$. All solution are obtained using the commercial solver Gurobi 5.6.2 \cite{gurobi} programmed in the YALMIP language \cite{YALMIP} in Matlab on a 64-bit Mac OS X 10.9.4 PC with a 1.8 Ghz Intel Core i5 processor and 4GB of RAM. The initial girth $8$ graphs were obtained using the labeling process for generalized quadrangles as described in \cite{GodsilRoyle2001} for graphs with degree $k=q+1$, where $q$ is a prime power, or the $t$-good structures from \cite{GacsHeger2008} for graphs with $k = q$. Starting from a $(k,8)$-graph where $k$ is odd, we tried to excise different trees with diameter $4$. For example, from the $(5,8)$-graph we successfully excised the following tree:
\begin{figure}[h!]
\centering
\begin{tikzpicture}
[scale=.8,auto=left,every node/.style={radius=10pt,circle,inner sep = 1.5pt,fill=black!100}]
\tikzset{Points/.style={draw,radius=10pt,rectangle,inner sep = 0.1pt,minimum width = 0.1cm,minimum height = 0.2cm,fill=black!20}}
\tikzset{Lines/.style={draw,radius=10pt,circle,inner sep = 0.1pt,minimum size = 0.1cm,fill=black!20}}
\node[Lines,label=below:{ }] (u) at (5,3.5) {};
\node[Lines,label=below:{ }] (v) at (7,3.5) {};
\draw (u) -- (v);
\foreach \x in {0,1,...,3} {
\node[Lines] (u\x) at (3,\x+2) {};
\pgfmathtruncatemacro\xplusone{ \x + 1}
\node[Lines] (v\x) at (9,\x+2) {};
}
\foreach \x in {0,1,...,3} {
\draw (u) -- (u\x);
\draw (v) -- (v\x);
\foreach \y in {0,1,...,3} {
\draw[black!50] (u\x) -- (2,\x+1.75 + \y/5);
%\draw (v\x) -- (10,\x+1.75 + \y/5);
}
}
\foreach \x in {2,3} {
%\draw (u) -- (u\x);
\draw (v) -- (v\x);
\foreach \y in {0,1,...,3} {
%\draw (u\x) -- (2,\x+1.75 + \y/5);
\draw[black!50] (v\x) -- (10,\x+1.75 + \y/5);
}
}
\foreach \x in {0,1} {
%\draw (u) -- (u\x);
\draw (v) -- (v\x);
\foreach \y in {0,1,...,3} {
%\draw (u\x) -- (2,\x+1.75 + \y/5);
\pgfmathtruncatemacro\xplusone{ \x + 1}
\node[Lines] (v1\x\y) at (12,2*\x + 1 + \y/2) {};
\draw (v\x) -- (v1\x\y);
\foreach \z in {0,1,...,3} {
%\draw (u\x) -- (2,\x+1.75 + \y/5);
\draw[black!50] (v1\x\y) -- (13,2*\x + 0.8 + \y/2 + \z/10);
}
}
}
\end{tikzpicture}
\caption{Tree $S$ with diameter $4$ consisting of $18$ vertices that was successfully excised from the $(5,8)$-cage.}\label{fig:ExcisionForGirth7NEW}
\end{figure}
We have tried to include more vertices, but then the program did not return a feasible solution. This was either because it determined that the program was infeasible, or because we manually aborted it after a certain period of time. The only situations where we had to manually abort the program was for some large sets $S$ for degrees $11$ and $13$, where we stopped the solver after $60$ minutes. This is because in all other cases, the solver returned a solution within $16$ minutes. The results from our computations are displayed in Table \ref{tab:ILPresults_odd}.
\begin{table}[htbp]
\centering
\caption{Results for individual excision on $(k,8)$-graphs for odd $k$.}
%\resizebox{1.0\textwidth}{!}{
\begin{tabular}{|r|r|r|r|r|r|r|}
\toprule
Degree & Order of & Order of & & & Time needed by & Total time\\
$k$ & $(k,8)$-graph & $(k,7)$-graph & $|S|$ & $|R|$ & Gurobi (sec) & \\
\midrule
$3$ & $30$ &$24$ &$6$ &$0$ & $<1$ & $<1$\\
$5$ & $170$ &$152$ &$18$ &$198$ & $<1$ & $2$ \\
$7$ & $658$ &$632$ &$26$ &$899$ & $4$ & $9$\\
$9$ & $1170$ &$1104$ &$66$ &$37632$ & $58$ & $79$ \\
$11$ & $2618$ &$2576$ &$42$ &$9267$ & $107$ & $228$ \\
$13$ & $4342$ &$4292$ &$50$ &$20743$ & $915$ & $1391$ \\
\bottomrule
\end{tabular}%
%}
\label{tab:ILPresults_odd}%
\end{table}%
Looking at the total running time, Gurobi clearly has the largest share. The total time depicted further includes: deleting the vertices and edges, calculating distance matrices, determine the forbidden combinations $R$ and setting up the model in YALMIP. Especially calculating the distance matrices might take considerably more time for graphs with more vertices. Note that for degree $9$ we could excise a bigger subset of vertices than for degree $11$ and $13$. This is probably due to the fact that the $(9,8)$-graph has a particularly nice structure as the incidence graph of a generalized quadrangle.
\section{Even degree graphs}\label{subsec:ExcisionIndividual_even}
For even degrees, we can do a similar kind of excision to the method for odd degrees as done in Section \ref{subsec:ExcisionIndividual}. However, the excised set of vertices can not be a tree as we did in the odd graphs (see Figure \ref{fig:ExcisionForGirth7NEW}) because we can only join an even number of neighbours by edges. When degree $k$ is even, one would need to join $k-1$ neighbours when excising a tree, which is an odd number. For even degrees $6\leq k\leq 14$ we therefore excise a different set of size $3k-1$. Only for the smallest even degree $k=4$ we could not excise more than $3k-2=10$ vertices. Note that for that degree the actual cage is known, which is not obtained via excision and contains $13$ vertices less than the $(4,8)$-cage \cite{Exooetal2011}. For the even degrees $6\leq k\leq 14$ the set of vertices that we remove is constructed as follows:
\begin{itemize}
\item Select a pair of vertices $\{u,v\}$ at distance $4$ from each other that have exactly $k$ vertices in common at distance $2$.
\item Remove $u$, $v$, their neighbours $N(u)$ and $N(v)$ and all but three of the vertices in $N_2(u,v)$, where $N_2(u,v)$ is the set of vertices that are at distance $2$ from both $u$ and $v$.
\end{itemize}
\begin{figure}[h!]
\centering
\begin{tikzpicture}
[scale=.8,auto=left,every node/.style={radius=10pt,circle,inner sep = 1.5pt,fill=black!100}]
\tikzset{Points/.style={draw,radius=10pt,rectangle,inner sep = 0.1pt,minimum width = 0.1cm,minimum height = 0.2cm,fill=black!20}}
\tikzset{Lines/.style={draw,radius=10pt,circle,inner sep = 0.1pt,minimum size = 0.1cm,fill=black!20}}
\node[Lines,label=below left:{ $u$}] (u) at (0,2.5) {};
\node[Lines,label=below right:{ $v$}] (v) at (8,2.5) {};
\foreach \x in {0,1,...,5} {
\node[Lines] (u\x) at (2,\x) {};
\node[Lines] (v\x) at (6,\x) {};
\node[Lines] (uv\x) at (4,\x) {};
\draw (u) -- (u\x);
\draw (v) -- (v\x);
\draw (u\x) -- (uv\x);
\draw (v\x) -- (uv\x);
}
\end{tikzpicture}
\caption{The set of excised vertices $S$ from the $(6,8)$-graph consists of vertices $u$ and $v$, their neighbours $N(u)$ and $N(v)$ and all but three of the vertices that are at distance $2$ of both $u$ and $v$.}\label{fig:ExcisionForGirth7_even}
\end{figure}
An example of such an excised set for degree $k=6$ is given in Figure \ref{fig:ExcisionForGirth7_even}. Note that for general even degree, we have no guarantee that there exist vertices $u,v$ with $|N_2(u,v)| = k$. However, in case $k=q+1$ and $q$ is a prime power, we are guaranteed that every vertex pair $\{u,v\}$ at distance $4$ has $|N_2(u,v)| = k$. This is due to the fact that every so-called point-pair in a generalized quadrangle is regular. For a more thorough description on point-pairs we refer the reader to the book by Payne and Thas \cite{PayneThas2009}. \\
\\
The next step is joining up the vertices so that every vertex has degree $k$ again. Let $S$ be the set of vertices consisting of $N(v)$, $N(v)$ and $N_2(u,v)$. Then every vertex in $S$ has $k-2$ neighbours in $V \backslash S$. Since $k$ is an even number, $k-2$ is even as well. The vertices in $N_2(u,v)$ that are not removed also have degree $k-2$ since they have one edge adjacent to $N(u)$ and one to $N(v)$. For all degrees $k\geq 6$ we have to leave exactly $3$ vertices from $N_2(u,v)$ in the remaining graph. \\
\\
The constraints we add and the set of forbidden combinations $R \subset \bar E \times \bar E$ are similar to the ones in program \eqref{program:individualexcision}. The paths through $V \backslash S$ that join two vertices in $S$ are of length at least $2$. Hence, every path containing three or more edges from $R$ has length $9$ again. Therefore, we can use the same definition for $R$, the set containing these forbidden combinations, as in \eqref{eq:forbiddencombinations}. The only significant difference is that there are now vertices with degree $k-2$, which need to be assigned two new edges instead of one. The computational results are given in Table \ref{tab:ILPresults_even}, in the same format as for odd degrees. In this table we have again $|S|$ as the size of the removed set of vertices and $|R|$ number of forbidden combinations. For all but the degrees $4$ and $6$ our results give new record graphs that improve the upper bound on the order of the cages previously known in the literature.
\begin{table}[htbp]
\centering
\caption{Results for individual excision on $(k,8)$-graphs for even $k$.}
%\resizebox{1.0\textwidth}{!}{
\begin{tabular}{|r|r|r|r|r|r|r|}
\toprule
Degree & Order of & Order of & & & Time needed by & Total time\\
$k$ & $(k,8)$-graph & $(k,7)$-graph & $|S|$ & $|R|$ & Gurobi (sec) & \\
\midrule
$4$ & $80$ &$70$ &$10$ &$12$ & $<1$ & $<1$ \\
$6$ & $312$ &$295$ &$17$ &$288$ & $<1$ & $3$\\
$8$ & $800$ &$777$ &$23$ &$989$ & $8$ & $15$ \\
$10$ & $1640$ &$1611$ &$29$ &$3108$ & $37$ & $68$ \\
$12$ & $2928$ &$2893$ &$35$ &$7555$ & $164$ & $301$ \\
$14$ & $4760$ &$4719$ &$41$ &$15625$ & $1004$& $1554$ \\
\bottomrule
\end{tabular}%
%}
\label{tab:ILPresults_even}%
\end{table}%
%\printbibliography
\bibliographystyle{plain}
\begin{thebibliography}{10}
\bibitem{AraujoPardo2010}
G.~Araujo-Pardo.
\newblock On upper bounds of odd girth cages.
\newblock {\em Discrete Mathematics}, 310(10-11):1622 -- 1626, 2010.
\bibitem{Biggs1998}
N.~L. Biggs.
\newblock Constructions for cubic graphs with large girth.
\newblock {\em Journal of Combinatorics}, 5:1--26, 1998.
\bibitem{ErdosSachs1963}
Paul Erd{\H{o}}s and Horst Sachs.
\newblock Regul{\"a}re graphen gegebener taillenweite mit minimaler knotenzahl.
\newblock {\em Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur.
Reihe}, 12:251--257, 1963.
\bibitem{ExooPersonalCommunication}
G.~Exoo.
\newblock personal communication, July 2014.
\bibitem{ExooJaycay2013}
Geoffrey Exoo and Robert Jajcay.
\newblock Dynamic cage survey.
\newblock {\em The Electronic Journal of Combinatorics}, 16, July 2013.
\bibitem{Exooetal2011}
Geoffrey Exoo, Brendan~D McKay, Wendy Myrvold, and Jacqueline Nadon.
\newblock Computational determination of (3, 11) and (4, 7) cages.
\newblock {\em Journal of Discrete Algorithms}, 9(2):166--169, 2011.
\bibitem{GacsHeger2008}
Andr{\'a}s G{\'a}cs and Tam{\'a}s H{\'e}ger.
\newblock On geometric constructions of (k, g)-graphs.
\newblock {\em Contributions to Discrete Mathematics}, 3(1):63--80, 2008.
\bibitem{GodsilRoyle2001}
C.~Godsil and G.F. Royle.
\newblock {\em Algebraic Graph Theory}.
\newblock Graduate Texts in Mathematics. Springer New York, New York, NY, 2001.
\bibitem{gurobi}
{\relax Inc}.~Gurobi~Optimization.
\newblock Gurobi optimizer reference manual, 2013.
\bibitem{YALMIP}
J.~L\"{o}fberg.
\newblock Yalmip : A toolbox for modeling and optimization in {MATLAB}.
\newblock In {\em Proceedings of the CACSD Conference}, Taipei, Taiwan, 2004.
\bibitem{McGee1960}
WF~McGee.
\newblock A minimal cubic graph of girth seven.
\newblock {\em Canadian Mathematical Bulletin}, 3:149--152, 1960.
\bibitem{McKayYuanshen}
Brendan McKay and Yang Yuanshen.
\newblock Electronic adjacency lists, accessed online at
\url{http://staffhome.ecm.uwa.edu.au/~00013890/ remote/cages/allcages.html}
on 3 July 2014.
\bibitem{PayneThas2009}
Stanley~E Payne and Joseph~Adolf Thas.
\newblock {\em Finite Generalized Quadrangles}, volume 110.
\newblock European Mathematical Society Publishing House, Zurich, 2 edition,
2009.
\bibitem{Sauer1967}
N~Sauer.
\newblock Extremaleigenschaften regul\"{a}rer graphen gegebener taillenweite, i
and ii.
\newblock {\em Sitzungsberichte \"{O}sterreich. Akad. Wiss. Math. Natur. Kl.,},
176:9--25; 176 (1967), 27--43, 1967.
\end{thebibliography}
\end{document}
% Style from sample tex file!!
%\section{Introduction}
%
%The reconstruction conjecture states that the multiset of unlabeled
%vertex-deleted subgraphs of a graph determines the graph, provided it
%has at least three vertices. This problem was independtly introduced
%by Ulam~\cite{Ulam} and Kelly~\cite{Kelly}. The reconstruction
%conjecture is widely studied
%\cite{Bollobas,FGH,HHRT,KSU,RM,RR,Stockmeyer} and is very interesting
%because...... See \cite{WikipediaReconstruction} for more about the
%reconstruction conjecture.
%
%\begin{definition}
% A graph is \emph{fabulous} if....
%\end{definition}
%
%\begin{theorem}
% \label{Thm:FabGraphs}
% All planar graphs are fabulous.
%\end{theorem}
%
%\begin{proof}
% Suppose on the contrary that some planar graph is not fabulous....
%\end{proof}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{Broglington Manifolds}
%
%This section describes background information about Broglington
%Manifolds.
%
%\begin{lemma}
% \label{lem:Technical}
% Broglington manifolds are abundant.
%\end{lemma}
%
%\begin{proof}
%
%\end{proof}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{Proof of Theorem~\ref{Thm:FabGraphs}}
%
%In this section we complete the proof of Theorem~\ref{Thm:FabGraphs}.
%
%\begin{proof}[Proof of Theorem~\ref{Thm:FabGraphs}]
%Let $G$ be a graph... Hence
% % use the amsmath align environment for multi-line equations
% \begin{align}
% |X| &= abcdefghijklmnopqrstuvwxyz \nonumber\\
% &= \alpha\beta\gamma
% \end{align}
% This completes the proof of Theorem~\ref{Thm:FabGraphs}.
%\end{proof}
%
%\begin{figure}[!h]
% \begin{center}
% % use \includegraphics to import figures
% % \includegraphics{filename}
% \end{center}
% \caption{\label{fig:InformativeFigure} Here is an informative
% figure.}
%\end{figure}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsection*{Acknowledgements}
%Thanks to Professor Querty for suggesting the proof of
%Lemma~\ref{lem:Technical}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file
%
%\begin{thebibliography}{10}
%
%\bibitem{Bollobas} B{\'e}la Bollob{\'a}s. \newblock Almost every
% graph has reconstruction number three. \newblock {\em J. Graph
% Theory}, 14(1):1--4, 1990.
%
%\bibitem{WikipediaReconstruction} Wikipedia contributors. \newblock
% Reconstruction conjecture. \newblock {\em Wikipedia, the free
% encyclopedia}, 2011.
%
%\bibitem{FGH} J.~Fisher, R.~L. Graham, and F.~Harary. \newblock A
% simpler counterexample to the reconstruction conjecture for
% denumerable graphs. \newblock {\em J. Combinatorial Theory Ser. B},
% 12:203--204, 1972.
%
%\bibitem{HHRT} Edith Hemaspaandra, Lane~A. Hemaspaandra,
% Stanis{\l}aw~P. Radziszowski, and Rahul Tripathi. \newblock
% Complexity results in graph reconstruction. \newblock {\em Discrete
% Appl. Math.}, 155(2):103--118, 2007.
%
%\bibitem{Kelly} Paul~J. Kelly. \newblock A congruence theorem for
% trees. \newblock {\em Pacific J. Math.}, 7:961--968, 1957.
%
%\bibitem{KSU} Masashi Kiyomi, Toshiki Saitoh, and Ryuhei Uehara.
% \newblock Reconstruction of interval graphs. \newblock In {\em
% Computing and combinatorics}, volume 5609 of {\em Lecture Notes in
% Comput. Sci.}, pages 106--115. Springer, 2009.
%
%\bibitem{RM} S.~Ramachandran and S.~Monikandan. \newblock Graph
% reconstruction conjecture: reductions using complement, connectivity
% and distance. \newblock {\em Bull. Inst. Combin. Appl.},
% 56:103--108, 2009.
%
%\bibitem{RR} David Rivshin and Stanis{\l}aw~P. Radziszowski.
% \newblock The vertex and edge graph reconstruction numbers of small
% graphs. \newblock {\em Australas. J. Combin.}, 45:175--188, 2009.
%
%\bibitem{Stockmeyer} Paul~K. Stockmeyer. \newblock The falsity of the
% reconstruction conjecture for tournaments. \newblock {\em J. Graph
% Theory}, 1(1):19--25, 1977.
%
%\bibitem{Ulam} S.~M. Ulam. \newblock {\em A collection of
% mathematical problems}. \newblock Interscience Tracts in Pure and
% Applied Mathematics, no. 8. Interscience Publishers, New
% York-London, 1960.
%
%\end{thebibliography}
%
%\end{document}