summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/tkz/tkz-berge/NamedGraphs/doc/latex/NamedGraphs-Cage.tex
blob: 520b38555f435b50d82b973b18045bbccf759711 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
\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