# 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 Odd  
Theorem 5: _When both \(n\) and \(s\) are odd,_  
\[diam(C_{n}(1,s))=\lceil\frac{\lambda}{2}\rceil+\frac{s+1}{2}-\min(\lceil\frac {\gamma+1}{2}\rceil,\lceil\frac{s-\gamma+2}{2}\rceil).\]  
Proof: Let us denote \(M\) as the minimum value between \(\lceil\frac{\gamma+1}{2}\rceil\) and \(\lceil\frac{s-\gamma+2}{2}\rceil\), and let \(i\) represent a vertex of \(C_{n}(1,s)\). We prove, by the same method as in Lemma 6, that for \(i\leq(\lfloor\frac{\lambda}{2}\rfloor+M)s\), \(d(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{s+1}{2}-M\). Then we prove, similarly as in Claim 1, that \(\lfloor\frac{\eta}{2}\rfloor\leq(\lfloor\frac{\lambda}{2}\rfloor+M)s<n\). Hence, by applying Lemma 5, we find that \(d(i)\leq\lceil\frac{\lambda}{2}\rceil+\frac{s+1}{2}-M\) for all vertices \(i\) in \(C_{n}(1,s)\). Hence, \(diam(C_{n}(1,s))\leq\lceil\frac{\lambda}{2}\rceil+\frac{s+1}{2}-\min(\lceil \frac{\gamma+1}{2}\rceil,\lceil\frac{s-\gamma+2}{2}\rceil)\). Let \(d=\lceil\frac{3}{2}\rceil+\frac{s+1}{2}-\min(\lceil\frac{\gamma+1}{2}\rceil,\lceil \frac{s-\gamma+2}{2}\rceil)\). Let \(R=\{1,2,\ldots,s-1\}\) be the set of all the possible values of \(\gamma\). This set can be partitioned into: \(R_{1}=\{2m-1:1\leq m\leq\lfloor\frac{s+3}{4}\rfloor\}\), \(R_{2}=\{2m-2:2\leq m\leq\lceil\frac{s+5}{4}\rceil\}\), \(R_{3}=\{s-2m+2:2\leq m\leq\lceil\frac{s-1}{4}\rceil\}\), and \(R_{4}=\{s-2m+3:2\leq m\leq\lceil\frac{s-1}{4}\rceil\}\). Moreover, \(R=R_{1}\cup R_{2}\cup R_{3}\cup R_{4}\). In fact, when \(\gamma\) is odd (i.e., \(\gamma\in\{R_{1},R_{3}\}\)), we have \(R_{1}=\{1,3,5,\ldots,2\lfloor\frac{s+3}{4}\rfloor-1\}\) and \(R_{3}=\{s-2\lceil\frac{s-1}{4}\rceil+2,\ldots,s-2\}\). It is easy to verify that, when \(s\) is odd, we obtain \(2\lfloor\frac{s+3}{4}\rfloor-1+2=s-2\lceil\frac{s-1}{4}\rceil+2\). Similarly, when \(\gamma\) is even, we have \(2\lceil\frac{s+5}{4}\rceil-2+2=s-2\lceil\frac{s-1}{4}\rceil+3\). **Case 1. **\(\gamma\in R_{1}\)  
Since \(\gamma\) is odd, \(\min(\lceil\frac{\gamma+1}{2}\rceil,\lceil\frac{s-\gamma+2}{2}\rceil)=\min( \frac{\gamma+1}{2},\frac{s-\gamma+2}{2})= \begin{cases}\frac{\gamma+1}{2}& \text{if }\gamma\leq\frac{s+1}{2},\\ \frac{s-\gamma+2}{2}&\text{otherwise}.\end{cases} \)  
However, we have \(\gamma=2m-1\) where \(1\leq m\leq\lfloor\frac{s+3}{4}\rfloor\). Thus, if \(s\equiv 1\pmod{4}\), then \(\gamma\leq\frac{s+1}{2}\). Otherwise, if \(s\equiv 3\pmod{4}\), then \(\gamma\leq\frac{s-1}{2}\). Hence, \(\min(\frac{\gamma+1}{2},\frac{s-\gamma+2}{2})=\frac{\gamma+1}{2}\). Moreover, we have \(\gamma\geq 1\), \(\lambda\geq 2\), \(s\geq 3\), and \(d=\frac{s+1}{2}-\frac{\gamma+1}{2}\). Let \(i=(\frac{\lambda}{2}-1)s+\frac{s-1}{2}+\frac{\gamma+1}{2}\) be a vertex of \(C_{n}(1,s)\). Since \(\gamma\leq\frac{s-1}{2}\), we have \(\frac{s-1}{2}+\frac{\gamma+1}{2}<s\). Note that \(\frac{\gamma+1}{2}-1\geq-\frac{\gamma+1}{2}+1\) because \(\gamma\geq 1\). Table 4 represents a simple calculation of the lengths \(\ell^{1}(i)\) to \(\ell^{4J}(i)\) provided in Lemma 3. Thus, by Lemma 4, we have \(d(i)=\ell^{2}(i)=d\). **Case 2. **\(\gamma\in R_{2}\)  
Since \(\gamma\) is even, \(\min(\lceil\frac{\gamma+1}{2}\rceil,\lceil\frac{s-\gamma+2}{2}\rceil)=\min( \frac{\gamma+2}{2},\frac{s-\gamma+3}{2})= \begin{cases}\frac{\gamma+2}{2}& \text{if }\gamma\leq\frac{s+1}{2},\\ \frac{s-\gamma+3}{2}&\text{if }\gamma\geq\frac{s+3}{2}.\end{cases} \)  
However, we have \(\gamma=2m-2\) where \(2\leq m\leq\lceil\frac{s+5}{4}\rceil\). Thus, if \(s\equiv 1\pmod{4}\), then \(\gamma\leq\frac{s+3}{2}\). Otherwise, if \(s\equiv 3\pmod{4}\), then \(\gamma\leq\frac{s+1}{2}\). Hence, \(\min(\frac{\gamma+1}{2},\frac{s-\gamma+2}{2})=\frac{\gamma+1}{2}\). Therefore, \(\gamma\geq 2\), \(\lambda\geq 3\), \(s\geq 3\), and \(d= \begin{cases}\frac{\lambda+1}{2}+\frac{s+1}{2}-\frac{s-\gamma+3}{2}&\text{if } \gamma=\frac{s+3}{2},\\ \frac{\lambda+1}{2}+\frac{s+1}{2}-\frac{\gamma+2}{2}&\text{if }\gamma\leq\frac{s+1}{2}. \end{cases} \)  
**Case 2.1.