# Edge Data Center Organization and Optimization by Using Cage Graphs
## 3 Overview of Graph Theory
### Outline of Cage Graphs  
An \((r,g)\)-cage graph is an undirected connected simple graph being \(r\) regular, which has the smallest possible number of nodes for its girth. Hence, all nodes have the same number of incident edges, given by \(r\), whereas the length of its shortest cycle is given by \(g\). Thus, every node has \(r\) neighbors and girth \(g\). There are some special cages, such as those compiled in the following list:  
* \((2,g)\) is the cycle graph \(C_{g}\) with \(g\) nodes;
* \((r,2)\) is the multigraph of \(r\) edges between just two nodes;
* \((r,3)\) is the complete graph \(K_{r+1}\) with \(r+1\) nodes;
* \((r,4)\) is the complete bipartite graph \(K_{r,r}\) with \(2r\) nodes. The number of nodes necessary to build an \((r,g)\)-cage graph bears a lower bound, called the Moore bound, and an upper bound, named the Sauer bound [30]. The former is presented in (9), whereas the latter is shown in (10). \begin{table}
\begin{tabular}{c c c} \hline
**Symbol** & **D Integrity** & **E Integrity** \\ \hline \(K_{n}\) & \(DI_{k}(K_{n})=(n^{2}-n)/2\) & \(El_{l}(K_{n})=(n^{2}+1)/2\) \\ \(\overline{K_{n}}\) & \(DI_{k}(\overline{K_{n}})=1\) & \(El_{l}(\overline{K_{n}})=1\) \\ \(K_{1,n}\) & \(DI_{k}(K_{1,n})=n\) & \(El_{l}(K_{1,n})=(n^{2}+n)/2\) \\ \(G_{S}\) & \(DI_{k}(G_{S})=4n-4\), if \(n\geq 3\) & \(El_{l}(G_{S})=5n-5\), if \(n\geq 3\) \\ \(K_{a,b}\) & \(\begin{cases}DI_{k}(K_{a,b})=\dfrac{3n^{2}-n}{2},\,\text{if}\,\,n=m;\\ \dfrac{n^{2}+2 mn-n}{2},\text{if}\,\,n\
eq m,n<m.\end{cases}\) & \(\begin{cases}El_{l}(K_{a,b})=\dfrac{3n^{2}+3n}{2},\,\text{if}\,\,n=m;\\ \dfrac{2 nm+m^{2}+m+2n}{2},\text{if}\,\,n\
eq m,n<m.\end{cases}\) \\ \hline \end{tabular}
\end{table} 
Table 2: \(D\) and \(E\) integrity of some well-known sorts of graphs. \[\text{cage}\;(r,g)\geq\text{Moore}\;(r,g)= \begin{cases}1+r\sum_{i=0}^{\frac{g-3}{ 2}}(r-1)^{i}\text{ if $g$ is odd}\\ 1+r\sum_{i=0}^{\frac{g-4}{2}}(r-1)^{i}+(r-1)^{\frac{g-2}{2}}\text{ if $g$ is even}\end{cases}  \tag{9}\]  
\[\text{cage}(r,g)\leq\text{Sauer}\;(r,g)= \begin{cases}2(r-2)^{g-2}\text{ if $g$ is odd}\\ 4(r-1)^{g-3}\text{ if $g$ is even}\end{cases}  \tag{10}\]  
There are some well-known Moore graphs [31], such as those where \(g=5\) and \(r=\{3,7,57\}\), or those where \(g=6\) and \(r=\{3,4\}\), although most \((r,g)\) cages contain a number of nodes between Moore \((r,g)\) and Sauer \((r,g)\). The most well-known cage graphs are those where \(r=3\), resulting in \((3,g)\)-cage graphs, which are presented in Table 3, where \(g\) values range from \(5\) to \(12\)[32]. Furthermore, the known values of \(g\) for \((r,g)\)-cage graphs with \(r=\{4,5,6,7\}\) are also listed in Table 4[33]. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Symbol** & **Name** & **Order** & **Instances** \\ \hline \((3,5)\) & [PERSON] graph & 10 & 1 \\ \((3,6)\) & [PERSON] graph & 14 & 1 \\ \((3,7)\) & [PERSON] graph & 24 & 1 \\ \((3,8)\) & [PERSON] graph & 30 & 1 \\ \((3,9)\) & First one: [PERSON] and [PERSON] graph & 58 & 18 \\ Remainder: [PERSON], [PERSON], and [PERSON] & & & \\  & [PERSON] 10-cage graph & 70 & 3 \\  & [PERSON] graph & & \\  & [PERSON]–[PERSON] graph & & \\ \((3,11)\) & [PERSON] 11-cage graph & 112 & 1 \\ \((3,12)\) & [PERSON] graph & 126 & 1 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: \((3,g)\)-cage graph classification for \(g=\{5\cdots 12\}\).