# 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 \(n\) Is Odd and \(s\) Is Even  
**Lemma 10**. : _When \(n\) is odd and \(s\) is even,_  
\[diam(C_{n}(1,s))\leq \begin{cases}\lceil\frac{\lambda}{2}\rceil+\frac{s-2}{2}& \text{if }\ \gamma\in\{1,s-1\},\\ \lfloor\frac{\lambda}{2}\rfloor+\frac{s-\gamma+1}{2}&\text{if }\ 3\leq\gamma\leq 2 \lceil\frac{s}{4}\rceil-1,\\ \lceil\frac{\lambda}{2}\rceil+\frac{\gamma-1}{2}&\text{otherwise.}\end{cases} \]  
Proof. : Since \(n\) is odd and \(s\) is even, \(\gamma\) is odd regardless of whether \(\lambda\) is even or odd. Let \(i\in V(C_{n}(1,s))\). **Case 1. \(\gamma\in\{1,s-1\}\)**  
For \(i\leq(\lfloor\frac{\lambda}{2}\rfloor+1)s\), we find that \(\ell^{3,1}(i)\leq\bar{r}_{1}+\lceil\frac{\lambda}{2}\rceil-1\) and \(\ell^{4,1}(i)\leq 1+s-\bar{r}_{1}+\lceil\frac{\lambda}{2}\rceil-1\). According to Lemma 4, if \(\bar{r}_{1}\leq\frac{s}{2}\), then \(d(i)\leq\ell^{3,1}(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{s-2}{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}{2}\). Therefore, we find that \(d(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{s-2}{2}\) for \(i\leq(\lfloor\frac{\lambda}{2}\rfloor+1)s\). By Lemma 5, if \(\lfloor\frac{\kappa}{2}\rfloor\leq(\lfloor\frac{\lambda}{2}\rfloor+1)s<n\), then \(d(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{s-2}{2}\) for all vertices \(i\) of \(C_{n}(1,s)\). Consequently, we will have \(diam(C_{n}(1,s))\leq\lceil\frac{\lambda}{2}\rceil+\frac{s-2}{2}\), which is the desired outcome. Hence, the remaining task is to prove that \(\lfloor\frac{\kappa}{2}\rfloor\leq(\lfloor\frac{\lambda}{2}\rfloor+1)s<n\), a proof that will be presented in the following claim. **Claim 3**. : \(\lfloor\frac{\kappa}{2}\rfloor\leq(\lfloor\frac{\lambda}{2}\rfloor+1)s<n\)_._  
Proof. : If \(\lambda\) is even, then,  
* \(\lfloor\frac{\kappa}{2}\rfloor-(\frac{\lambda}{2}+1)s\leq\frac{\kappa}{2}-( \frac{\lambda}{2}+1)s\leq\frac{\lambda s+\gamma}{2}-\frac{\lambda s+2s}{2}\leq \frac{\gamma-2s}{2}<0\). * \((\frac{\lambda}{2}+1)s-n=\frac{\lambda s+2-2\lambda s-2\gamma}{2}=\frac{s(2- \lambda)-2\gamma}{2}<0\). (\(\lambda\geq 2\) even, so \(2-\lambda<0\)) Otherwise, if \(\lambda\) is odd, then,
* \(\lfloor\frac{\kappa}{2}\rfloor-(\frac{\lambda-1}{2}+1)s\leq\frac{\kappa}{2}-( \frac{\lambda-1}{2}+1)s\leq\frac{\lambda s+\gamma}{2}-\frac{\lambda s-s+2s}{2} \leq\frac{\gamma-s}{2}<0\). * \((\frac{\lambda-1}{2}+1)s-n=\frac{\lambda s-s+2s-2\gamma}{2}=\frac{s(1-\lambda )-2\gamma}{2}<0\). (\(\lambda\geq 2\) even, so \(1-\lambda<0\))  
**Case 2. \(3\leq\gamma\leq 2\lceil\frac{s}{2}\rceil-1\)**  
For \(i\leq(\lceil\frac{\lambda}{2}\rceil+\frac{\gamma-1}{2})s\), we find that \(\ell^{3,1}(i)\leq\bar{r}_{1}+\lceil\frac{\lambda}{2}\rceil-\frac{\gamma-1}{2}\) and \(\ell^{4,1}(i)\leq 1+s-\bar{r}_{1}+\lceil\frac{\lambda}{2}\rceil-\frac{\gamma-1}{2}\). According to Lemma 4, if \(\bar{r}_{1}\leq\frac{s}{2}\), then \(d(i)\leq\ell^{3,1}(i)\leq\lfloor\frac{\lambda}{2}\rfloor+\frac{s-\gamma+1}{2}\); otherwise, if \(\bar{r}_{1}\geq\frac{s}{2}+1\), then \(d(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{s-\gamma+1}{2}\). Therefore, we find that \(d(i)\leq\lfloor\frac{\lambda}{2}\rfloor+\frac{s-\gamma+1}{2}\) for \(i\leq(\lceil\frac{\lambda}{2}\rceil+\frac{\gamma-1}{2})s\). By Lemma 5, if \(\lfloor\frac{\kappa}{2}\rfloor\leq(\lceil\frac{\lambda}{2}\rceil+\frac{\gamma-1}{2} )s<n\), then we will have \(diam(C_{n}(1,s))\leq\lfloor\frac{\lambda}{2}\rfloor+\frac{s-\gamma+1}{2}\). Hence, the remaining task is to prove that \(\lfloor\frac{\kappa}{2}\rfloor\leq(\lceil\frac{\lambda}{2}\rceil+\frac{\gamma-1}{2} )s<n\), a proof that will be presented in the following claim. Claim 4**. : \(\lfloor\frac{\kappa}{2}\rfloor\leq(\lceil\frac{\lambda}{2}\rceil+\frac{\gamma-1}{2} )s<n\)_._  
Proof. : If \(\lambda\) is even, then,  
* \(\lfloor\frac{\kappa}{2}\rfloor-(\frac{\lambda}{2}+\frac{\gamma-1}{2})s\leq\frac{ \kappa}{2}-(\frac{\lambda}{2}+\frac{\gamma-1}{2})s\leq\frac{\gamma+s-\gamma s}{2}<0\).