# A New Algorithm for Computing the Distance and the Diameter in Circulant Graphs
## 1 Introduction
Hence, our focus in this paper is on the connection set \(S=\{1,s\}\), where \(s\) is an integer satisfying \(2\leq s\leq\lfloor\frac{n}{2}\rfloor\). Theorem 1: _Let \(n\geq 6\) and let \(2\leq s_{1}<s_{2}\leq\lfloor\frac{n}{2}\rfloor\) such that \(gcd(n,s_{1})=1\) or \(gcd(n,s_{2})=1\). Therefore, \(C_{n}(s_{1},s_{2})\) is isomorphic to \(C_{n}(1,s)\), where \(s.s_{1}\equiv s_{2}\pmod{n}\) or \(s.s_{1}\equiv n-s_{2}\pmod{n}\)._  
Proof: Without loss of generality, we assume that \(gcd(n,s_{1})=1\) (the same reasoning applies when \(gcd(n,s_{2})=1\)). Let \(V(C_{n}(1,s))=\{0,1,\ldots,n-1\}\). We define the following permutation:  
\[\sigma: V(C_{n}(1,s))\longrightarrow\{0,1,\ldots,n-1\}\] \[i\longmapsto\sigma(i)=i.s_{1}\pmod{n}\]  
By construction, \(\sigma\) is surjective. Let \(i,j\in V(C_{n}(1,s))\) such that \(\sigma(i)=\sigma(j)\). So, \(i.s_{1}\equiv j.s_{1}\pmod{n}\). Which means that \((i-j)s_{1}\equiv 0\pmod{n}\). Since \(gcd(n,s_{1})=1\) and \(s_{1}\
eq 0\), we get \(i-j=0\). Thus, \(i=j\). Consequently, \(\sigma\) is bijective. Since \(C_{n}(1,s)\) and \(C_{n}(s_{1},s_{2})\) are vertex-transitive graphs, it suffices to verify that for a vertex \(i\
eq 0\), \((0,i)\in E(C_{n}(1,s))\) if and only if \((0,\sigma(i))\in C_{n}(s_{1},s_{2})\). Recall that in this proof, all calculations are done modulo \(n\). Let \(i\in V(C_{n}(1,s))\). If \((0,i)\in E(C_{n}(1,s))\) then \(|i|_{n}\in\{1,s\}\). \(|i|_{n}=1\) means that \(i=1\) or \(i=n-1\). Moreover, \(\sigma(1)=s_{1}\) and \(\sigma(n-1)=(n-1).s_{1}\equiv-s_{1}\pmod{n}\). Therefore, \((0,\sigma(i))\in E(C_{n}(s_{1},s_{2}))\). If \(|i|_{n}=s\) then \(i=s\) or \(i=n-s\). Thus, \(\sigma(s)=s.s_{1}\equiv s_{2}\pmod{n}\). So, \(\sigma(s)\in S\). Also, \(\sigma(n-s)=(n-s).s_{1}\equiv-s_{2}\pmod{n}\), i.e., \(\sigma(n-s)\in S\). Therefore, if \(|i|_{n}=s\) then \((0,\sigma(i))\in E(C_{n}(s_{1},s_{2}))\). Conversely, if \((0,\sigma(i))\in E(C_{n}(s_{1},s_{2})))\) then, \(|\sigma(i)|_{n}\in\{s_{1},s_{2}\}\). \(|\sigma(i)|_{n}=s_{1}\) means that \(\sigma(i)=s_{1}\) or \(n-\sigma(i)=s_{1}\). So, \(i.s_{1}=s_{1}\) or \(n-i.s_{1}=s_{1}\). Since \(gcd(n,s_{1})=1\), \(i=1\equiv(\bmod{n})\) or \(-i=1\equiv(\bmod{n})\). Thus, \(i=1\) or \(i=n-1\). Hence, \((0,i)\in E(C_{n}(1,s))\). If \(|\sigma(i)|_{n}=s_{2}\), then \(\sigma(i)=s_{2}\) or \(n-\sigma(i)=s_{2}\). So, \(i.s_{1}=s_{2}\) or \(n-i.s_{1}=s_{2}\). Thus, \(i.s_{1}=s.s_{1}\) or \(-i.s_{1}=s_{1}\). Since \(gcd(n,s_{1})=1\), \(i=s\equiv(\bmod{n})\) or \(-i=s\equiv(\bmod{n})\). Therefore, \(i=s\equiv(\bmod{n})\) or \(i=n-s\equiv(\bmod{n})\). Hence, \((0,i)\in E(C_{n}(1,s))\). Consequently, \(C_{n}(s_{1},s_{2})\) is isomorphic to \(C_{n}(1,s)\). Subsequently, we will focus only on the following problem. **Problem 1**. : _Given \(n,s\), determine \(diam(C_{n}(1,s))\)._  
To solve this problem, we develop a new algorithm in this paper that calculates the diameter of circulant graphs \(C_{n}(1,s)\) without implementing any graph. This innovative method, which aids in finding distances within a circulant graph, enables us to derive exact formulas for the diameter of \(C_{n}(1,s)\) across a wide range of \(n\) and \(s\) combinations. (See Table 1, where \(n=\lambda s+\gamma\), \(\lambda=\lfloor\frac{n}{2}\rfloor\), \(n\equiv\gamma\pmod{s}\), \(s=a\gamma+b\), \(a=\lfloor\frac{s}{\gamma}\rfloor\), \(s\equiv b\pmod{\gamma}\), \(p_{0}=\lfloor\frac{\lambda+\gamma}{2}\rfloor\), \(p_{1}=\lfloor\frac{\gamma-b+(a+1)\lambda+1}{2}\rfloor\), \(p_{2}=\lfloor\frac{\gamma+b+(a-1)\lambda+1}{2}\rfloor\), \(p_{3}=\lfloor\frac{b+a\lambda+1}{2}\rfloor\), \(p_{4}=(\gamma+b)(a\lambda-\lambda+1)\), and \(e=\min\{\max\{p_{1},p_{3}\},\max\{p_{0},p_{2}\}\}\).