# Edge Data Center Organization and Optimization by Using Cage Graphs
## 3 Overview of Graph Theory
### Integrity of Graphs  
Communication networks need higher degrees of stability to perform properly, which means lower levels of vulnerability due to potential failure occurrences. In this sense, it may seem clear that network efficiency reduces when some nodes or edges are down. This leads to the definition of graph integrity (\(I(G)\), also known as vertex integrity) [22] as a measure of the vulnerability of a graph \(G\), as shown in (1), where \(m(G-S)\) describes the order of the largest component of \(G-S\), and \(|S|\) is the order of the given subset \(S\) of \(V(G)\). ore resilient graphs are obtained when integrity values are higher, meaning more nodes need to be deleted. Order refers to the number of nodes of a graph, whereas size refers to the number of its links. \[I(G)=min\{|S|+\ m(G-S):S\subseteq V(G)\} \tag{1}\]  
Furthermore, any subset \(S\subseteq V(G)\) may be called the \(I\)th set of \(G\) if (2) applies. \[I(G)=|S|+\ m(G-S) \tag{2}\]  
Otherwise, edge integrity (\(I^{\prime}(G)\)) may be defined in an analogous way by swapping \(V(G)\) with \(E(G)\)[23], as shown in (3). \[I^{\prime}(G)=min\{|X|+\ m(G-X):X\subseteq E(G)\} \tag{3}\]  
There is an intrinsic relationship between both values related to a given graph, such that vertex integrity \(I(G)\) never exceeds edge integrity \(I^{\prime}(G)\). Hence, if \(G\) is a nontrivial connected graph of order \(n\), then (4) applies [24]. \[2\leq I(G)\leq I^{\prime}(G)\leq n \tag{4}\]  
Taking all this into consideration, integrity may be a more suitable parameter to measure network reliability, as it does not only account for node connectivity when some of those nodes are removed, but it also takes into account the remaining nodes that are functioning [25], which may give a more complete picture regarding network stability. The values of integrity of some simple types of graphs are provided in Table 1[26], whereas combinations of those result in diverse values of integrity [27]. Additionally, from the definition proposed for vertex integrity, two extra parameters computationally useful may be defined [28]: \(D_{k}(G)\) (5) and \(E_{l}(G)\) (6), which better denote the stability of a network. \[D_{k}(G)=min\{|S|:S\subset V(G),m(G-S)\leq k\},\ \text{where}\ k=\{1\cdots|V(G)|-1\} \tag{5}\]  
\[E_{l}(G)=min\{m(G-S):S\subset V(G),|S|=l\},\ \text{where}\ l=\{0\cdots|V(G)|-1\} \tag{6}\] \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Graph Name** & **Symbol** & **Vertex** & **Edge** \\  & & **Integrity** & **Integrity** \\ \hline Complete graph & \(K_{n}\) & \(I(K_{n})=n\) & \(I^{\prime}(K_{n})=n\) \\ Null graph & \(\overline{K_{n}}\) & \(I(\overline{K_{n}})=1\) & \(I^{\prime}(\overline{K_{n}})=1\) \\ Star graph & \(K_{1,n}\) & \(I(K_{1,n})=2\) & \(I^{\prime}(K_{1,n})=n+1\) \\ Path graph & \(P_{n}\) & \(I(P_{n})=[2\sqrt{n}+1]-2\) & \(I^{\prime}(P_{n})=[2\sqrt{n}]-1\) \\ Cycle graph & \(C_{n}\) & \(I(C_{n})=[2\sqrt{n}]-1\) & \(I^{\prime}(C_{n})=[2\sqrt{n}]\) \\ Complete bipartite graph & \(K_{a,b}\) & \(I(K_{a,b})=1+\min\{a,b\}\) & \(I(K_{a,b})=mt+n\) \\ Wheel graph & \(W_{n}\) & \(I(W_{n})=[2\sqrt{n}-1]\) & \(I(W_{n})=[2\sqrt{n}]+1\) \\ Spider graph & \(G_{5}\) & \(I(G_{5})=[(n+1)/2]\) & \(I(G_{5})=((n+3)/2]\) \\ \(n\)-cube & \(G_{n}\) & \(I(Q_{n})=1+2^{n-1}\) & \(I(Q_{n})=2^{n}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Integrity of some well-known kinds of graphs. \(D_{1}(G)=\alpha(G)\), meaning that the vertex cover of graph \(G\), as well as \(E_{0}(G)=m(G)\), represents the maximum order of any component of \(G\) additionally, \(D_{|V(G)|}(G)=0\) and \(E_{|V(G)|}(G)=0\). The concepts of \(D_{k}(G)\) and \(E_{l}(G)\) lead to the definition of \(D\) integrity (7) and \(E\) integrity (8), respectively [29]. \[DI_{k}(G)=\sum_{k=1}^{|V(G)|-1}D_{k}(G) \tag{7}\]  
\[E_{l}(G)=\sum_{l=0}^{|V(G)|-1}E_{l}(G) \tag{8}\]  
The values of these new kinds of integrity of some simple graphs are cited in Table 2, whereas combinations of these account for different values, whose calculation still represents an open problem in graph theory.