# 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 Even and \(s\) Is Odd  
**Lemma 6**. : _When \(n\) is even and \(s\) is odd,_  
\[diam(C_{n}(1,s))\leq\lceil\frac{\lambda}{2}\rceil+\frac{s+1}{2}-\min(\lceil \frac{\gamma}{2}\rceil,\lceil\frac{s-\gamma+1}{2}\rceil).\]  
Proof. : Let us denote \(M\) as the minimum value between \(\lceil\frac{\gamma}{2}\rceil\) and \(\lceil\frac{s-\gamma+1}{2}\rceil\), and let \(i\) represent a vertex of \(C_{n}(1,s)\). 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+1}{2}\), then \(\min\left(\ell^{3,1}(i),\ell^{4,1}(i)\right)=\ell^{3,1}(i)\); otherwise, \(\min(\ell^{3,1}(i),\ell^{4,1}(i))=\ell^{4,1}(i)\). For \(i\leq(\lfloor\frac{\lambda}{2}\rfloor+M)\)s, we find that \(\ell^{3,1}(i)\leq\bar{r}_{1}+\lceil\frac{\lambda}{2}\rceil-M\) and \(\ell^{4,1}(i)\leq 1+s-\bar{r}_{1}+\lceil\frac{\lambda}{2}\rceil-M\). If \(\bar{r}_{1}\leq\frac{s+1}{2}\), then \(d(i)\leq\ell^{3,1}(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{s+1}{2}-M\); otherwise, \(d(i)\leq\ell^{4,1}(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{s+1}{2}-M\). Therefore, \(d(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{s+1}{2}-M\) for \(i\leq(\lfloor\frac{\lambda}{2}\rfloor+M)\)s. By Lemma 5, if \(\frac{n}{2}\leq(\lfloor\frac{\lambda}{2}\rfloor+M)\)s<n\), then \(d(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{s+1}{2}-M\) 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+1}{2}-M\), which is the desired outcome. Hence, the remaining task is to prove that \(\frac{n}{2}\leq(\lfloor\frac{\lambda}{2}\rfloor+M)\)s \(<n\), a proof that will be presented in the following claim. Claim 1.: \(\frac{n}{2}\leq(\lfloor\frac{\lambda}{2}\rfloor+M)\)s \(<n\). Proof. : It is worth noting that if \(\gamma\) is even (or odd), given that \(n\) is even and \(s\) is odd, we conclude that \(\lambda\) is also even (or odd). Also, if \(\gamma\leq\frac{s+1}{2}\), then \(M=\lceil\frac{\gamma}{2}\rceil\); otherwise, \(M=\lceil\frac{s-\gamma+1}{2}\rceil\). Therefore, we will consider the following two cases:  
**Case 1. **\(\gamma\leq\frac{s+1}{2}\)  
In this case, we have  
\[(\lfloor\frac{\lambda}{2}\rfloor+M)\)s = \((\lfloor\frac{\lambda}{2}\rfloor+\lceil\frac{\gamma}{2}\rceil)s\) \(= \begin{cases}(\frac{\lambda-1}{2}+\frac{\gamma+1}{2})s,&\text{if $\gamma$ is odd}\\ (\frac{\lambda}{2}+\frac{\gamma}{2})s,&\text{if $\gamma$ is even}\end{cases} \) \(=(\frac{\lambda+\gamma}{2})s\). Thus,  
* \(\frac{n}{2}-(\frac{\lambda+\gamma}{2})s=\frac{\lambda s+\gamma}{2}-\frac{ \lambda s+\gamma s}{2}=\frac{\gamma(1-s)}{2}<0\). * \((\frac{\lambda+\gamma}{2})s-n=(\frac{\lambda+\gamma}{2})s-(\lambda s+\gamma)= \frac{s(\gamma-\lambda)-2\gamma}{2}<0\). (Since \(\gamma<\lambda\), \(\gamma-\lambda<0\))  
**Case 2. **\(\gamma>\frac{s+1}{2}\)  
In this case,  
\[(\lfloor\frac{\lambda}{2}\rfloor+M)\)s = (\lfloor\frac{\lambda}{2}\rfloor+\lceil\frac{s-\gamma+1}{2} \rceil)s\] \[= (\frac{\lambda+s-\gamma+1}{2})s.\]  
Hence,  
* \(\frac{n}{2}-(\frac{\lambda+s-\gamma+1}{2})\)s = \(\frac{\lambda s+\gamma}{2}-\frac{\lambda s+s^{2}-\gamma s+s}{2}=\frac{(\gamma- s)+(\gamma s-s^{2})}{2}\leq 0\). (\(\gamma s<s^{2}\))
* \(n=(\frac{\lambda+s-\gamma+1}{2})s-(\lambda s+\gamma)=\frac{s(s-\lambda-\gamma)+(s -2\gamma)}{2}<0\). (We have \(\gamma>\frac{s+1}{2}\), so \(2\gamma-s>1\). Thus, \(s-2\gamma<0\). On the other hand, since \(\lambda>\gamma\) and \(\gamma>\frac{s+1}{2}\), then \(\lambda>\frac{s+1}{2}\). Thus, \(s-\lambda<\frac{s-1}{2}\). Moreover, we have \(-\gamma<\frac{-s-1}{2}\). Hence, \(s-\lambda-\gamma<\frac{s-1}{2}+\frac{-s-1}{2}<0\)\(\Box\)  
Lemma 7: _Suppose \(n\) is even and \(s\) is odd. There is a vertex \(i\) in \(C_{n}(1,s)\) such that,_  
\[d(i)=\lceil\frac{\lambda}{2}\rceil+\frac{s+1}{2}-\min(\lceil\frac{\gamma}{2} \rceil,\lceil\frac{s-\gamma+1}{2}\rceil).\]  
Proof.