\newpage\section{Cage}\label{cage} %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> %<–––––––––––––––––––– Cage –––––––––––––––––––––––––––––––> %<––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––> \begin{NewMacroBox}{Cage Graphs}{} \medskip From Wikipedia \url{http://en.wikipedia.org/wiki/Cage_(graph_theory)}\\ \emph{In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.\\ Formally, an $(r,g)$-graph is defined to be a graph in which each vertex has exactly $r$ neighbors, and in which the shortest cycle has length exactly $g$. It is known that an $(r,g)$-graph exists for any combination of $r \geq 2$ and $g \geq 3$. An $(r,g)$-cage is an $(r,g)$-graph with the fewest possible number of vertices, among all $(r,g)$-graphs.} \medskip From MathWorld \url{http://mathworld.wolfram.com/CageGraph.html}\\ \emph{A $(r,g)$-cage graph is a $v$-regular graph of girth $g$ having the minimum possible number of nodes. When $v$ is not explicitly stated, the term "$g$-cage" generally refers to a $(3,g)$-cage.} \href{http://mathworld.wolfram.com/topics/GraphTheory.html}% {\textcolor{blue}{MathWorld}} by \href{http://en.wikipedia.org/wiki/Eric_W._Weisstein}% {\textcolor{blue}{E.Weisstein}} \medskip Examples : \medskip \begin{tabular}{ll} \bottomrule $(r,g)$ & Names \\ \midrule $(3,3)$ & complete graph $K_4$ \\ $(3,4)$ & complete bipartite graph $K_{3,3}$ Utility Graph\ref{bipart} \\ $(3,5)$ & Petersen graph \ref{petersen} \\ $(3,6)$ & Heawood graph \ref{heawood} \\ $(3,7)$ & McGee graph \ref{mcgee} \\ $(3,8)$ & Levi graph \ref{levi} \\ $(3,10)$ & Balaban 10-cage \ref{balaban} \\ $(3,11)$ & Balaban 11-cage \ref{balaban} \\ $(3,12)$ & Tutte 12-cage \\ $(4,3)$ & complete graph $K_5$ \\ $(4,4)$ & complete bipartite graph $K_{4,4}$ \ref{bipart} \\ $(4,5)$ & Robertson graph\ref{robertson} \\ $(4,6)$ & Wong (1982)\ref{wong} \\ \end{tabular} \end{NewMacroBox} \endinput