# A New Algorithm for Computing the Distance and the Diameter in Circulant Graphs
## 2 Definitions and Notations
\begin{table}
\begin{tabular}{c c c c c c} \hline \(P(0,6)\) & **Representation of \(P(0,6)\)** & \(\ell_{a}(P(0,6))\) & \(\ell_{c}(P(0,6))\) & \(\ell(P(0,6))\) \\ \hline \(=(2a^{+},1c^{+})\) & \(0\leadsto^{a^{+}}1\leadsto^{a^{+}}2\leadsto^{c^{+}}6\) & 2 & 1 & 3 \\ \hline \(=(2a^{-},2c^{+})\) & \(0\leadsto^{a^{-}}9\leadsto^{a^{-}}8\leadsto^{c^{+}}2\leadsto^{c^{+}}6\) & 2 & 2 & 4 \\ \hline \(=(0,4c^{+})\) & \(0\leadsto^{c^{+}}4\leadsto^{c^{+}}8\leadsto^{c^{+}}2\leadsto^{c^{+}}6\) & 0 & 4 & 4 \\ \hline \(=(0,1c^{-})\) & \(0\leadsto^{c^{-}}6\) & 0 & 1 & 1 \\ \hline \end{tabular}
\end{table} 
Table 2: Examples of paths leading from the vertex \(0\) to the vertex \(6\) in \(C_{10}(1,4)\). \(C_{n}(1,s)\) that traverses all its outer edges before entering its inner edges, or vice versa, as represented below. \[P(i)= \begin{cases}((\alpha-\beta)a^{+},(\gamma-\lambda)c^{+})&\text{ if }\quad\alpha\geq\beta\text{ and }\gamma\geq\lambda,\\ ((\beta-\alpha)a^{-},(\lambda-\gamma)c^{-})&\text{ if }\quad\alpha\leq\beta \text{ and }\gamma\leq\lambda,\\ ((\alpha-\beta)a^{+},(\lambda-\gamma)c^{-})&\text{ if }\quad\alpha\geq\beta \text{ and }\gamma\leq\lambda,\\ ((\beta-\alpha)a^{-},(\gamma-\lambda)c^{+})&\text{ if }\quad\alpha\leq\beta \text{ and }\gamma\geq\lambda.\end{cases} \]  
Thus,  
\[\ell(P(i))= \begin{cases}(\alpha-\beta)+(\gamma-\lambda)&\text{ if }\quad\alpha\geq\beta\text{ and }\gamma\geq\lambda,\\ (\beta-\alpha)+(\lambda-\gamma)&\text{ if }\quad\alpha\leq\beta\text{ and }\gamma\leq\lambda,\\ (\alpha-\beta)+(\lambda-\gamma)&\text{ if }\quad\alpha\geq\beta\text{ and } \gamma\leq\lambda,\\ (\beta-\alpha)+(\gamma-\lambda)&\text{ if }\quad\alpha\leq\beta\text{ and } \gamma\geq\lambda.\end{cases} \]  
It is evident that \(\ell(P(i))\leq\ell(\mathcal{W})\). Therefore, for all vertices \(i\in V(C_{n}(1,s))\) in the graph \(C_{n}(1,s)\), there exists a path leading from vertex \(0\) to vertex \(i\) by traversing all its outer edges before entering its inner edges, or vice versa. Assume now that \(P^{\prime}(i)\) is an arbitrary path in \(C_{n}(1,s)\) leading from vertex \(0\) to vertex \(i\) by traversing \(\alpha^{\prime}a^{+}\), \(\beta^{\prime}a^{-}\), \(\gamma^{\prime}c^{+}\) and \(\lambda^{\prime}c^{-}\). In the same manner, it can be proven that there exists a path \(P(i)\) equivalent to \(P^{\prime}(i)\) leading from vertex \(0\) to vertex \(i\) by traversing all its outer edges before entering its inner edges, or vice versa. **Example 4**. : _Let us consider the graph \(C_{10}(1,4)\) presented in Figure 2. Without loss of generality, let \(\mathcal{W}\) be an arbitrary walk in \(C_{10}(1,4)\) leading from vertex \(0\) to vertex \(6\), with \(\mathcal{W}\) taking the edges \(1a^{+},1a^{-},2c^{+}\), and \(3c^{-}\). The representation of \(\mathcal{W}\) is as follows:_  
\[0\leadsto^{a^{+}}1\leadsto^{c^{+}}5\leadsto^{c^{+}}9\leadsto^{a^{-}}8 \leadsto^{c^{-}}4\leadsto^{c^{-}}0\leadsto^{c^{-}}6.\]  
_By Lemma 2, there exists a path \(P(6)\) leading from vertex \(0\) to vertex \(6\), defined as \(P(6)=((1-1)a^{+},(3-2)c^{-})=(0,1c^{-})\). We observe that \(\ell(P(6))=1\), which is less than \(\ell(\mathcal{W})=7\). Thus, for vertex \(6\), there exists a path \(P(6)\) that traverses all its outer edges before entering its inner edges._  
_In the same graph of Example 1, \(P_{3}(6)\) is an arbitrary path in \(C_{10}(1,4)\) leading from vertex \(0\) to vertex \(6\), by taking the edges \(1a^{+},1a^{-}\) and \(4c^{+}\). The representation of \(P_{3}(6)\) is as follows:_  
\[0\leadsto^{a^{+}}1\leadsto^{c^{+}}5\leadsto^{c^{+}}9\leadsto^{c^{+}}3\leadsto^ {a^{-}}2\leadsto^{c^{+}}6.\]  
_There exists the path \(P_{4}(6)\), from Example 1, leading from vertex \(0\) to vertex \(6\), defined as \(P_{4}(6)=((1-1)a^{+},4c^{+})=(0,4c^{+})\). We observe that \(\ell(P_{4}(6))=4\), which is less than \(\ell(P_{3}(6))=6\). Thus, for vertex \(6\), there exists a path \(P_{4}(6)\) that traverses all its outer edges before entering its inner edges._  
**Notation 2**. : _Let \(i\) be a vertex of \(C_{n}(1,s)\), and let \(t\) be an integer.