# A New Algorithm for Computing the Distance and the Diameter in Circulant Graphs
## 4 Diameter Formulas for Circulant Graphs
### Diameter of \(C_{n}(1,s)\) When Both \(n\) and \(s\) Are Even  
**Lemma 8**. : _When both \(n\) and \(s\) are even,_  
\[diam(C_{n}(1,s))\leq \begin{cases}\lceil\frac{\lambda}{2}\rceil+\frac{s-\gamma}{2 }&\text{if }\ \gamma\leq 2\lceil\frac{s-2}{4}\rceil,\\ \lfloor\frac{\lambda}{2}\rfloor+\frac{\gamma}{2}&\text{otherwise}.\end{cases} \]Proof. : Since both \(n\) and \(s\) are even, \(\gamma\) is also even regardless of whether \(\lambda\) is even or odd. Let \(i\) represent a vertex of \(C_{n}(1,s)\). **Case 1. **\(\gamma\leq 2\lceil\frac{s-2}{4}\rceil\)  
According to Lemma 4, we find that \(d(i)\leq\min(\ell^{3,1}(i),\ell^{4,1}(i))\), where \(\ell^{3,1}(i)=\bar{r}_{1}+\lfloor\frac{n-i}{s}\rfloor\) and \(\ell^{4,1}(i)=1+s-\bar{r}_{1}+\lfloor\frac{n-i}{s}\rfloor\). It is worth noting that if \(\bar{r}_{1}\leq\frac{s}{2}\), then \(\min(\ell^{3,1}(i),\ell^{4,1}(i))=\ell^{3,1}(i)\); otherwise, if \(\bar{r}_{1}\geq\frac{s}{2}+1\), then \(\min(\ell^{3,1}(i),\ell^{4,1}(i))=\ell^{4,1}(i)\). For \(i\leq(\lfloor\frac{\lambda}{2}\rfloor+\frac{7}{2})s\), we find that \(\ell^{3,1}(i)\leq\bar{r}_{1}+\lceil\frac{\lambda}{2}\rceil-\frac{7}{2}\) and \(\ell^{4,1}(i)\leq 1+s-\bar{r}_{1}+\lceil\frac{\lambda}{2}\rceil-\frac{7}{2}\). If \(\bar{r}_{1}\leq\frac{s}{2}\), then \(d(i)\leq\ell^{3,1}(i)\leq\lceil\frac{3}{2}\rceil+\frac{s}{2}-\frac{7}{2}\); otherwise, if \(\bar{r}_{1}\geq\frac{s}{2}+1\), then \(d(i)\leq\ell^{4,1}(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{s}{2}-\frac{7}{2}\). Therefore, \(d(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{s}{2}-\frac{7}{2}\) for \(i\leq(\lfloor\frac{\lambda}{2}\rfloor+\frac{7}{2})s\). By Lemma 5, if \(\frac{n}{2}\leq(\lfloor\frac{\lambda}{2}\rfloor+\frac{7}{2})s<n\), then \(d(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{s}{2}-\frac{7}{2}\) for all vertices \(i\) of \(C_{n}(1,s)\). Consequently, we will have \(diam(C_{n}(1,s))\leq\lceil\frac{3}{2}\rceil+\frac{s}{2}-\frac{7}{2}\), which is the desired outcome. Hence, the remaining task is to prove that \(\frac{n}{2}\leq(\lfloor\frac{\lambda}{2}\rfloor+\frac{7}{2})s<n\), a proof that will be presented in the following claim. **Claim 2**. : \(\frac{n}{2}\leq(\lfloor\frac{\lambda}{2}\rfloor+\frac{7}{2})s<n\)_._  
Proof. : If \(\lambda\) is even, then,  
* \(\frac{n}{2}-(\frac{\lambda}{2}+\frac{7}{2})s=\frac{\lambda s+7}{2}-\frac{ \lambda s+7s}{2}=\frac{7(1-s)}{2}<0\). * \((\frac{\lambda}{2}+\frac{7}{2})s-n=\frac{\lambda s+7s-2\lambda s-27}{2}=\frac{ \lambda(7-\lambda)-27}{2}<0\). (\(\gamma<\lambda\), so \(\gamma-\lambda<0\)) Otherwise, if \(\lambda\) is odd, then
* \((\frac{\lambda-1}{2}+\frac{7}{2})s-n=\frac{\lambda s-s+7s-2\lambda s-27}{2}= \frac{s(7-\lambda)-s-27}{2}<0\). (\(\gamma<\lambda\), so \(\gamma-\lambda<0\))
* \(\frac{n}{2}-(\frac{\lambda-1}{2}+\frac{7}{2})s=\frac{\lambda s+7}{2}-\frac{ \lambda s-s+7s}{2}=\frac{\gamma+s-7s}{2}<0\). (Assume that \(\gamma+s-\gamma s>0\), i.e., \(s(1-\gamma)+\gamma>0\), which implies that \(s(\gamma-1)<\gamma\). Thus, \(s<\frac{\gamma}{\gamma-1}\). Contradiction with the fact that \(s>\gamma\). Hence, \(\gamma+s-\gamma s<0\))  
**Case 2. **\(\gamma>2\lceil\frac{s-2}{4}\rceil\)  
For \(i\leq(\lfloor\frac{\lambda}{2}\rfloor+\frac{7}{2})s\), we have \(\ell^{1}(i)\leq\lfloor\frac{\lambda}{2}\rfloor+\frac{7}{2}\). Therefore, according to Lemma 4, we find that \(d(i)\leq\ell^{1}(i)\leq\lfloor\frac{\lambda}{2}\rfloor+\frac{7}{2}\). Moreover, as per the previous claim, we showed that \(\frac{n}{2}\leq(\lfloor\frac{\lambda}{2}\rfloor+\frac{7}{2})s<n\), thus, by Lemma 5, \(d(i)\leq\lfloor\frac{\lambda}{2}\rfloor+\frac{7}{2}\) for all vertices \(i\) of \(C_{n}(1,s)\). Consequently, \(diam(C_{n}(1,s))\leq\lfloor\frac{\lambda}{2}\rfloor+\frac{7}{2}\). **Lemma 9**. : _Suppose that both \(n\) and \(s\) are even. There is a vertex \(i\) in \(C_{n}(1,s)\) such that,_  
\[d(i)= \begin{cases}\lceil\frac{\lambda}{2}\rceil+\frac{s-\gamma}{2}&\text{ if }\ \gamma\leq 2\lceil\frac{s-2}{4}\rceil,\\ \lfloor\frac{\lambda}{2}\rfloor+\frac{\gamma}{2}&\text{ otherwise.}\end{cases} \]  
Proof. : Let \(d=