# 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
\((\frac{\lambda}{2}+\frac{\gamma-1}{2})s-n=\frac{s(\gamma-\lambda)-s-2\gamma}{2}<0\). Otherwise, if \(\lambda\) is odd, then, \(\lfloor\frac{n}{2}\rfloor-(\frac{\lambda+\gamma}{2})s\leq\frac{n}{2}-(\frac{ \lambda+\gamma}{2})s\leq\frac{\gamma(1-s)}{2}<0\). \((\frac{\lambda+\gamma}{2})s-n=\frac{s(\gamma-\lambda)-2\gamma}{2}<0\). \(\Box\)  
**Case 3. **\(\frac{s}{2}\leq\gamma<s-1\)  
For \(i\leq(\lceil\frac{\lambda}{2}\rceil+\frac{\gamma-1}{2})s\), we have \(\ell^{1}(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{\gamma-1}{2}\). Therefore, according to Lemma 4, we find that \(d(i)\leq\ell^{1}(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{\gamma-1}{2}\). Moreover, as per the previous claim, we showed that \(\lfloor\frac{n}{2}\rfloor\leq(\lceil\frac{\gamma}{2}\rceil+\frac{\gamma-1}{2} )s<n\), thus, by Lemma 5, \(d(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{\gamma-1}{2}\) for all vertices \(i\) of \(C_{n}(1,s)\). Consequently, \(diam(C_{n}(1,s))\leq\lceil\frac{\lambda}{2}\rceil+\frac{\gamma-1}{2}\). \(\Box\)  
**Lemma 11**. : _Suppose that \(n\) is odd and \(s\) is even. There is a vertex \(i\) in \(C_{n}(1,s)\) such that_  
\[d(i)= \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. ** Let \(d= \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} \)  
**Case 1. **\(\gamma\in\{1,s-1\}\)  
If \(\gamma=1\) then, \(\lambda\geq 2\), \(s\geq 4\), and \(d=\lceil\frac{\lambda}{2}\rceil+\frac{s-2}{2}\). Let \(i=(\lceil\frac{\lambda}{2}\rceil-1)s+\frac{s}{2}\) be a vertex of \(C_{n}(1,s)\). Table 5 represents a simple calculation of the lengths \(\ell^{1}(i)\) to \(\ell^{4,l}(i)\) provided in Lemma 3. Thus, by Lemma 4, we have \(d(i)=\ell^{1}(i)=d\). If \(\gamma=s-1\), then \(\lambda\geq s,s\geq 4\), and \(d=\lceil\frac{\lambda}{2}\rceil+\frac{s-2}{2}\). Let \(i=(\lceil\frac{\lambda}{2}\rceil-1)s+\frac{s}{2}\) be a vertex of \(C_{n}(1,s)\). By a simple calculation of the lengths \(\ell^{1}(i)\) to \(\ell^{4,l}(i)\) represented in Lemma 3, and by applying Lemma 4, we obtain \(d(i)=\ell^{1}(i)=d\). **Case 2. **\(3\leq\gamma\leq 2\lceil\frac{s}{4}\rceil-1\)  
If \(\lambda\) is even, then \(\lambda\geq 4\), \(s\geq 4\), and \(d=\frac{\lambda}{2}+\frac{s}{2}-\frac{\gamma-1}{2}\). Let \(i=(\frac{\lambda}{2}-\frac{\gamma-1}{2})s+\frac{s}{2}+1\) be a vertex of \(C_{n}(1,s)\). Note that since \(s\geq 4\), we have \(\frac{s}{2}+1<s\). By a simple calculation of the lengths \(\ell^{1}(i)\) to \(\ell^{4,l}(i)\) represented in Lemma 3, and by applying Lemma 4, we obtain \(d(i)=\ell^{2}(i)=d\). If \(\lambda\) is odd then, \(\gamma\geq 3\), \(\lambda\geq 5\), \(s\geq 4\), and \(d=\frac{\lambda-1}{2}+\frac{s}{2}-\frac{\gamma-1}{2}\). Let \(i=\frac{\lambda-1}{2}s+\frac{\gamma-1}{2}+\frac{s}{2}+1\) be a vertex of \(C_{n}(1,s)\). Note that since \(\gamma\leq\lceil\frac{s}{4}\rceil-1\) and \(s\geq 4\), we get \(\frac{\gamma-1}{2}+\frac{s}{2}+1<s\). Bya simple calculation of the lengths \(\ell^{1}(i)\) to \(\ell^{4,t}(i)\) represented in Lemma 3, and by applying Lemma 4, we obtain \(d(i)=\ell^{2}(i)=d\). **Case 3. **\(2\lceil\frac{s}{4}\rceil\leq\gamma<s-1\)  
We have \(\gamma\geq 3\), \(\lambda\geq 4\), \(s\geq 4\), and \(d=\lceil\frac{\lambda}{2}\rceil+\frac{\gamma-1}{2}\). Let \(i=\lceil\frac{\lambda}{2}\rceil s+\frac{\gamma-1}{2}\) be a vertex of \(C_{n}(1,s)\). Note that since \(s>\gamma\), we have \(s-\frac{\gamma-1}{2}>\frac{\gamma+1}{2}\). By a simple calculation of the lengths \(\ell^{1}(i)\) to \(\ell^{4,t}(i)\) represented in Lemma 3, and by applying Lemma 4, we obtain \(d(i)=\ell^{1}(i)=d\). This completes the proof. Thus, the following theorem follows from Lemmas 10 and 11.