# A New Algorithm for Computing the Distance and the Diameter in Circulant Graphs
## 2 Definitions and Notations
_An outer (or inner) edge connecting the vertices_ \(i\) _and_ \(j\) _and following the clockwise_ \((+)\) _or counterclockwise_ \((-)\) _direction is represented as_ \(i\leadsto^{a^{\pm}}j\) _(or_ \(i\leadsto^{c^{\pm}}j\)_), respectively._
2. _The length of the path_ \(P(i,j)\) _is denoted by_ \(\ell(P(i,j))\)_, the number of outer edges in_ \(P(i,j)\) _is represented by_ \(\ell_{a}(P(i,j))\)_, and the number of inner edges in_ \(P(i,j)\) _is denoted by_ \(\ell_{c}(P(i,j))\)_. Thus,_ \(\ell(P(i,j))=\ell_{a}(P(i,j))+\ell_{c}(P(i,j))\)_._  
**Example 1**. : _Let us focus on the graph \(C_{10}(1,4)\) presented in Figure 2._  
_If we choose an arbitrary vertex within the graph, such as vertex \(6\), there will exist multiple paths from vertex \(0\) to vertex \(6\). For illustrative purposes, we provide several of these paths in Table 2._  
Figure 2: The circulant graph \(C_{10}(1,4)\). **Definition 3**. : _Let \(i,j\in V(C_{n}(1,s))\). Let \(P(i,j)\) and \(Q(i^{\prime},j^{\prime})\) be two paths in \(C_{n}(1,s)\). \(P(i,j)\) is equivalent to \(Q(i^{\prime},j^{\prime})\), denoted \(P(i,j)\approx Q(i^{\prime},j^{\prime})\), if and only if \(\ell(P(i,j))=\ell(Q(i^{\prime},j^{\prime}))\), \(\ell_{a}(P(i,j))=\ell_{a}(Q(i^{\prime},j^{\prime}))\), \(\ell_{c}(P(i,j))=\ell_{c}(Q(i^{\prime},j^{\prime}))\), and that \(P(i,j)\) and \(Q(i^{\prime},j^{\prime})\) take the same direction._  
**Example 2**. : _In Example 1, \(P(6,9)=(1a^{-},1c^{+})\) is equivalent to \(P(0,3)=(1a^{-},1c^{+})\) because \(\ell(P(6,9))=\ell(P(0,3))=2\), \(\ell_{a}(P(6,9))=\ell_{a}(P(0,3))=1\), \(\ell_{c}(P(6,9))=\ell_{c}(P(0,3))=1\), and that \(P(6,9)\) and \(P(0,3)\) take the same direction._  
**Lemma 1**. : _Consider two vertices \(i\) and \(j\) belonging to the vertex set \(V(C_{n}(1,s))\) of the circulant graph \(C_{n}(1,s)\). Let \(P(i,j)\) and \(Q(i,j)\) be two distinct paths within \(C_{n}(1,s)\). The relation denoted by \(\approx\) is an equivalence relation defined on the set of paths in \(C_{n}(1,s)\)._  
Proof. : The proof is immediate. **Observations**  
* Let us recall that since circulants belong to the family of Cayley graphs, any undirected circulant graph is vertex-transitive. Consequently, for any pair of vertices \(i\) and \(j\) within \(C_{n}(S)\), their distance, denoted as \(d(i,j)\), can be equivalently expressed as \(d(0,z)\), where \(z= \begin{cases}j-i,&\text{if }i<j,\\ n-i+j,&\text{otherwise}.\end{cases} \)
* Since circulants are vertex-transitive and symmetric, the maximum distance among all pairs of vertices in \(C_{n}(1,s)\) must occur for vertices \(i\) such that \(1\leq i\leq\lfloor\frac{n}{2}\rfloor\). However, \(d(0,1)=d(0,n-1)=1\). Thus, we have \(diam(C_{n}(1,s))=\max\{d(0,i):\,2\leq i\leq\lfloor\frac{n}{2}\rfloor\}\). Henceforth, in this work, we specifically focus on paths leading from vertex \(0\) to another vertex \(i\) in \(C_{n}(1,s)\), denoted as \(P(i)\). The distance of \(P(i)\) is represented as \(d(i)\). **Example 3**. : _Consider the graph \(C_{10}(1,4)\) depicted in Figure 2. Here, we provide examples of some equivalent paths in \(C_{10}(1,4)\):_  
* \(P(6,9)=(1a^{-},1c^{+})\) _is equivalent to_ \(P(3)=(1a^{-},1c^{+})\)_;_
* \(P(6,2)=(0,1c^{-})\) _is equivalent to_ \(P(6)=(0,1c^{-})\)_;_  
**Lemma 2**. : _For any vertex \(i\) in \(C_{n}(1,s)\), there exists a path that connects vertex \(0\) to \(i\), following a sequence of traversing all its outer edges before proceeding to its inner edges, or conversely, traversing all its inner edges before entering its outer edges._  
Proof. : Let \(i\) be a vertex of \(C_{n}(1,s)\). Without loss of generality, suppose that \(\mathcal{W}\) is an arbitrary walk in \(C_{n}(1,s)\) leading from vertex \(0\) to vertex \(i\) by traversing \(\alpha a^{+}\), \(\beta a^{-}\), \(\gamma c^{+}\) and \(\lambda c^{-}\), of length \(\ell(\mathcal{W})=\alpha+\beta+\gamma+\lambda\). In such a case, there exists a path \(P(i)\) in