# 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
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\). If \(s>5\) then, \(\gamma\geq 3\), \(\lambda\geq 5\), and \(d=\frac{\lambda+1}{2}+\frac{s+1}{2}-\frac{\gamma+1}{2}\). Let \(i=\frac{\lambda+1}{2}s+\frac{\gamma+1}{2}+\frac{s+1}{2}\) be a vertex of \(C_{n}(1,s)\). Since \(s>5\) and \(\gamma\leq\frac{s+1}{2}\), we obtain \(\frac{\gamma+1}{2}+\frac{s+1}{2}<s\). Note that \(\frac{\gamma-1}{2}-1\geq-\frac{\gamma+1}{2}+2\) because \(\gamma\geq 3\). By a simple calculation of the lengths \(\ell^{1}(i)\) to \(\ell^{4J}(i)\) represented in Lemma 3, and by applying Lemma 4, we obtain \(d(i)=\ell^{2}(i)=d\). **Case 2. **\(\gamma\in R_{2}\)  
Since \(\gamma\) is even, \(\min(\lceil\frac{\gamma}{2}\rceil,\lceil\frac{s-\gamma+1}{2}\rceil)=\min( \frac{\gamma}{2},\frac{s-\gamma+1}{2})= \begin{cases}\frac{\gamma}{2}&\text{if }\ \gamma\leq \frac{s+1}{2},\\ \frac{s-\gamma+1}{2}&\text{otherwise}.\end{cases} \) Moreover, \(\gamma=2m\) where \(1\leq m\leq\lfloor\frac{s+3}{4}\rfloor\). Thus, for \(s\) odd, we obtain \(\gamma\leq\frac{s+3}{2}\). Hence, we have \(\gamma\geq 2\), \(\lambda\geq 4\), \(s\geq 3\), and \(d= \begin{cases}\frac{\lambda}{2}+\frac{s+1}{2}-\frac{s-\gamma+1}{2}&\text{if }\ \gamma=\frac{s+3}{2},\\ \frac{\lambda}{2}+\frac{s+1}{2}-\frac{\gamma}{2}&\text{if }\ \gamma\leq\frac{s+1}{2}.\end{cases} \) **Case 2.1. **\(\gamma=\frac{s+3}{2}\)  
In this case, \(d=\frac{\lambda}{2}+\frac{\gamma}{2}\). Let \(i=\frac{\lambda}{2}s+\frac{\gamma}{2}\) be a vertex of \(C_{n}(1,s)\). Note that since \(s>\gamma\), we obtain \(s-\frac{\gamma}{2}>\frac{\gamma}{2}\). By a simple calculation of the lengths \(\ell^{1}(i)\) to \(\ell^{4J}(i)\) represented in Lemma 3, and by applying Lemma 4, we obtain \(d(i)=\ell^{1}(i)=d\). **Case 2.2. **\(\gamma\leq\frac{s+1}{2}\)  
If \(s=3\), then \(\gamma=2\), \(\lambda\geq 4\), and \(d=\frac{\lambda}{2}+1\). Let \(i=(\frac{\lambda}{2}+1)s\) be a vertex of \(C_{n}(1,s)\). By a simple calculation of the lengths \(\ell^{1}(i)\) to \(\ell^{4J}(i)\) represented in Lemma 3, and by applying Lemma 4, we obtain \(d(i)=\ell^{2}(i)=d\). If \(s>3\), then \(\gamma\geq 2\), \(\lambda\geq 4\), and \(d=\frac{\lambda}{2}+\frac{s+1}{2}-\frac{\gamma}{2}\). Let \(i=\frac{\lambda}{2}s+\frac{s+1}{2}+\frac{\gamma}{2}\) be a vertex of \(C_{n}(1,s)\). Since \(s>3\) and \(\gamma\leq\frac{s+1}{2}\), we have \(\frac{s+1}{2}+\frac{\gamma}{2}<s\). Note that \(\frac{\gamma}{2}-1\geq-\frac{\gamma}{2}+1\) because \(\gamma\geq 2\). By a simple calculation of the lengths \(\ell^{1}(i)\) to \(\ell^{4J}(i)\) represented in Lemma 3, and by applying Lemma 4, we obtain \(d(i)=\ell^{2}(i)=d\). **Case 3. **\(\gamma\in R_{3}\)  
In this case, \(\gamma=s-2m+2\) where \(2\leq m\leq\lceil\frac{s-1}{4}\rceil\). If \(s\equiv 1\pmod{4}\), then \(\gamma\geq\frac{s+5}{2}\). Otherwise, if \(s\equiv 3\pmod{4}\), then \(\gamma\geq\frac{s+3}{2}\). Since \(\gamma\) is odd and \(\gamma\geq\frac{s+1}{2}\), we get \(\min(\lceil\frac{\gamma}{2}\rceil,\lceil\frac{s-\gamma+1}{2}\rceil)=\min( \frac{\gamma+1}{2},\frac{s-\gamma+2}{2})=\frac{s-\gamma+2}{2}\). Therefore, \(\gamma\geq 3\), \(\lambda\geq 5\), \(s\geq 7\) (when \(s\leq 5\), \(R_{3}=\emptyset\)), and \(d=\frac{\lambda+1}{2}+\frac{s+1}{2}-\frac{s-\gamma+2}{2}\). Let \(i=(\frac{\lambda+1}{2}-\frac{s-\gamma+2}{2})s+\frac{s+1}{2}\) be a vertex \(C_{n}(1,s)\). By a simple calculation of the lengths \(\ell^{1}(i)\) to \(\ell^{4J}(i)\) represented in Lemma 3, and by applying Lemma 4, we obtain \(d(i)=\ell^{1}(i)=\ell^{2}(i)=d\). **Case 4. **\(\gamma\in R_{4}\)  
Here, we have \(\gamma=s-2m+1\) where \(1\leq m\leq\lceil\frac{s-5}{4}\rceil\). If \(s\equiv 1\pmod{4}\), then \(\gamma\geq\frac{s+7}{2}\). Otherwise, if \(s\equiv 3\pmod{4}\), then \(\gamma\geq\frac{s+5}{2}\). Moreover, since \(\gamma\) is even and \(\gamma\geq\frac{s+1}{2}\), we have \(\min(\lceil\frac{\gamma}{2}\rceil,\lceil\frac{s-\gamma+1}{2}\rceil)=\min( \frac{\gamma}{2},\frac{s-\gamma+1}{2})=\frac{s-\gamma+1}{2}\).