# 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
: Let \(d=\lceil\frac{\lambda}{2}\rceil+\frac{s+1}{2}-\min(\lceil\frac{\gamma}{2} \rceil,\lceil\frac{s-\gamma+1}{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:1\leq m\leq\lfloor\frac{s+3}{4}\rfloor\}\), \(R_{3}=\{s-2m+2:2\leq m\leq\lceil\frac{s-1}{4}\rceil\}\), and \(R_{4}=\{s-2m+1:1\leq m\leq\lceil\frac{s-5}{4}\rceil\}\). Note that \(R_{3}=R_{4}=\emptyset\) when \(s\leq 5\). 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\lfloor\frac{s+3}{4}\rfloor+2=s-2\lceil\frac{s-5}{4}\rceil+1\). **Case 1. **\(\gamma\in R_{1}\)  
Since \(\gamma\) is odd, \(\min(\lceil\frac{\gamma}{2}\rceil,\lceil\frac{s-\gamma+1}{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, \(\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, \(\lambda\) is odd and \(\lambda>\gamma\geq 1\). Thus, \(\lambda\geq 3\). Therefore, when \(\gamma\in R_{1}\), \(d=\frac{\lambda+1}{2}+\frac{s-1}{2}-\frac{\gamma+1}{2}+1\). **Case 1.1. **\(\gamma=1\)  
In this case, \(d=\frac{\lambda+s}{2}\). Let \(i=\frac{\lambda-1}{2}s+\frac{s+1}{2}\) be a vertex of \(C_{n}(1,s)\). We have,  
* \(\ell^{1}(i)=\ell^{2}(i)=\frac{\lambda-1}{2}+\frac{s+1}{2}=d\); Let \(1\leq t\leq\frac{s}{gcd(n,s)}\) be an integer. We have \(tn+i=(t\lambda+\frac{\lambda-1}{2})s+t+\frac{s+1}{2}\). If \(t+\frac{s+1}{2}<s\) then,
* \(\ell^{1,t}(i)=t(\lambda+1)+\frac{\lambda-1}{2}+\frac{s+1}{2}>d\); If \(t+\frac{s+1}{2}\geq s\), i.e., \(t\geq\frac{s-1}{2}\), then \(tn+i=(t\lambda+\frac{\lambda-1}{2}+\lambda^{\prime})s+\gamma^{\prime}\) where \(\lambda^{\prime}\geq 1\), \(\gamma^{\prime}\geq 0\) and \(t+\frac{s+1}{2}=\lambda^{\prime}s+\gamma^{\prime}\). * \(\ell^{1,t}(i)=t\lambda+\frac{\lambda-1}{2}+\lambda^{\prime}+\gamma^{\prime} \geq t\lambda+\frac{\lambda+1}{2}>t+\frac{\lambda+1}{2}\). So, \(\ell^{1,t}(i)>\frac{s-1}{2}+\frac{\lambda+1}{2}\). Thus, \(\ell^{1,t}(i)>d\);
* \(\ell^{2,t}(i)=1+s-\gamma^{\prime}+t\lambda+\frac{\lambda-1}{2}+\lambda^{ \prime}\geq t\lambda+\frac{\lambda+1}{2}+1\). Thus, \(\ell^{2,t}(i)>d\); We have \(tn-i=((t-1)\lambda+\frac{\lambda+1}{2})s+t-\frac{s+1}{2}\). If \(t-\frac{s+1}{2}<0\), then \(tn-i=((t-1)\lambda+\frac{\lambda-1}{2})s+t+\frac{s-1}{2}\), \(\frac{\lambda-1}{2}\))s \(t+t\)\(\frac{s-1}{2}\),
* \(\ell^{3,t}(i)=(t-1)(\lambda+1)+\frac{\lambda+1}{2}+\frac{s-1}{2}\geq\frac{ \lambda+1}{2}+\frac{s-1}{2}\geq d\);
* \(\ell^{4,t}(i)=(t-1)(\lambda-1)+\frac{\lambda-1}{2}+\frac{s+1}{2}\geq\frac{ \lambda+1}{2}+\frac{s-1}{2}\geq d\); If \(0\leq t-\frac{s+1}{2}<s\), i.e., \(t\geq\frac{s+1}{2}\), then \(tn-i=((t-1)\lambda+\frac{\lambda+1}{2})s+t-\frac{s+1}{2}\). * \(\ell^{3,t}(i)=(t-1)\lambda+\frac{\lambda+1}{2}+t-\frac{s+1}{2}\geq(t-1)\lambda+ \frac{\lambda+1}{2}>t+\frac{\lambda-1}{2}\). So, \(\ell^{3,t}(i)>d\). * \(\ell^{4,t}(i)=1+s-(t-\frac{s+1}{2})+(t-1)\lambda+\frac{\lambda+1}{2}\geq(t-1) \lambda+\frac{\lambda+1}{2}+1\). Thus, \(\ell^{4,t}(i)>d\). Thus, by Lemma 4, we have \(d(i)=\ell^{1}(i)=\ell^{2}(i)=d\). **Case 1.2. **\(\gamma\geq 3\)  
If \(s=5\) then, we have \(\gamma=3\), \(\lambda\geq 5\), and \(d=\frac{\lambda+1}{2}+1\). Let \(i=(\frac{\lambda+1}{2}+1)\)s be a vertex of \(C_{n}(1,s)\).