# A New Algorithm for Computing the Distance and the Diameter in Circulant Graphs
## 3 Algorithm Computing the Diameter of Circulant Graphs  
Our objective is to establish formulas that yield precise values for the diameter of \(C_{n}(1,s)\) across all potential combinations of \(n\) and \(s\). Given that the diameter represents the greatest distance between any pair of vertices, and the distance corresponds to the shortest path, we have thoroughly examined the characteristics of paths in \(C_{n}(1,s)\). Consequently, we have discovered the existence of numerous equivalent paths leading from vertex 0 to another vertex \(i\) within \(C_{n}(1,s)\). Our approach revolves around identifying and characterizing this equivalent class of paths in \(C_{n}(1,s)\), which allows us to derive the exact values for the diameter of the graph. **Lemma 3**: \(\!\!\!\)**. ** _Let \(t\) be an integer such that \(1\leq t\leq\frac{s}{gcd(n,s)}\). For every vertex \(i\) of \(C_{n}(1,s)\), there exists a class of pairwise non-equivalent paths \(\mathcal{C}=\{P^{1}(i),P^{2}(i)\), \(P^{1,t}(i)\), \(P^{2,t}(i)\), \(P^{3,t}(i)\), \(P^{4,t}(i)\}\) such that_  
* \(P^{1}(i)=(ra^{+},qc^{+})\) _of length_ \(\ell^{1}(i)=r+q\)_._
* \(P^{2}(i)=((s-r)a^{-},(q+1)c^{+})\) _of length_ \(\ell^{2}(i)=1+s-r+q\)_._
* \(P^{1,t}(i)=(r_{t}a^{+},q_{t}c^{+})\) _of length_ \(\ell^{1,t}(i)=r_{t}+q_{t}\)_._
* \(P^{2,t}(i)=((s-r_{t})a^{-},(q_{t}+1)c^{+})\) _of length_ \(\ell^{2,t}(i)=1+s-r_{t}+q_{t}\)_._
* \(P^{3,t}(i)=(\bar{r}_{t}a^{-},\bar{q}c^{-})\) _of length_ \(\ell^{3,t}(i)=\bar{r}_{t}+\bar{q}_{t}\)_._
* \(P^{4,t}(i)=((s-r_{t})a^{+},(q_{t}+1)c^{-})\) _of length_ \(\ell^{4,t}(i)=1+s-r_{t}+q_{t}\)_._  
Let \(i\) be a vertex of \(C_{n}(1,s)\) and \(t\) be an integer such that \(1\leq t\leq\frac{s}{gcd(n,s)}\). By the definition of \(r\), we have \(i=qs+r\). In this case, we consider the path \(P(i)\) represented as follows \(0\leadsto^{a^{+}}1\leadsto^{a^{+}}2\leadsto^{a^{+}}\cdots\leadsto^{a^{+}}r \leadsto^{c^{+}}r+s\leadsto^{c^{+}}r+2s\leadsto^{c^{+}}\cdots\leadsto^{c^{+}}r +qs=i\). We have \(P^{1}(i)=(ra^{+},qc^{+})\) and, \(\ell^{1}(i)=r+q\). Remark that \(i\) can be also written as \(i=(q+1)s+(r-s)\). We consider, in this case, the path \(P(i)\) represented as follows \(0\leadsto^{a^{+}}n-1\leadsto^{a^{+}}n-2\leadsto^{a^{+}}\cdots\leadsto^{a^{-}}n -(s-r)\leadsto^{c^{+}}n-(s-r)+s\leadsto^{c^{+}}n-(s-r)+2s\leadsto^{c^{+}} \cdots\leadsto^{c^{+}}n-(s-r)+(q+1)s=n+i\) (\(\equiv i\mod n\)). We have \(P^{2}(i)=((s-r)a^{-},(q+1)c^{+})\) and, \(\ell^{2}(i)=1+s-r+q\). By the definition of \(q_{t}\), we have \(tn+i=q_{t}s+r_{t}\). In this case, we consider the path \(P(i)\) represented as follows \(0\leadsto^{a^{+}}1\leadsto^{a^{+}}2\leadsto^{a^{+}}\cdots\leadsto^{a^{+}}r \leadsto^{c^{+}}r_{t}+s\leadsto^{c^{+}}r_{t}+2s\leadsto^{c^{+}}\cdots\leadsto^{c^{+}} r_{t}+q_{t}s=tn+i\) (\(\equiv i\mod n\)). We have \(P^{3,t}(i)=(r_{t}a^{+},q_{t}c^{+})\) and, \(\ell^{1,t}(i)=r_{t}+q_{t}\). Remark that \(i\) can be written as \(tn+i=(q_{t}+1)s+(r_{t}-s)\). In this case, we consider the path \(P(i)\) represented as follows \(0\leadsto^{a^{+}}n-1\leadsto^{a^{+}}n-2\leadsto^{a^{+}}\cdots\leadsto^{a^{-}}n -(s-r_{t})\leadsto^{c^{+}}n-(s-r_{t})+s\leadsto^{c^{+}}n-(s-r_{t})+2s\leadsto^{c^{+ }}\cdots\leadsto^{c^{+}}n-(s-r_{t})+(q_{t}+1)s=(t+1)n+i\) (\(\equiv i\mod n\)). We have \(P^{2,t}(i)=((s-r_{t})a^{-},(q_{t}+1)c^{+})\) and, \(\ell^{2,t}(i)=1+s-r_{t}+q_{t}\). By the definition of \(\bar{q}_{t}\), we have \(tn-i=q_{t}s+r_{t}\). In this case, we consider the path \(P(i)\) represented as follows \(0\leadsto^{a^{+}}n-1\leadsto^{a^{+}}n-2\leadsto^{a^{+}}\cdots\leadsto^{a^{-}}-r _{t}\leadsto^{c^{-}}-\bar{r}_{t}-s\leadsto^{c^{-}}-\bar{r}_{t}-2s\leadsto^{c^{-}} \cdots\leadsto^{c^{-}}-\bar{r}_{t}-\tilde{q}_{t}s=-tn+i\) (\(\equiv i\mod n\)). We have \(P^{3,t}(i)=(\bar{r}_{t}a^{-},\bar{q}_{t}c^{-})\) and, \(\ell^{3,t}(i)=\bar{r}_{t}+\bar{q}_{t}\). Remark that \(i\) can be written as \(tn-i=(\bar{q}_{t}+1)s+(\bar{r}_{t}-s)\).