# A New Algorithm for Computing the Distance and the Diameter in Circulant Graphs
## 2 Definitions and Notations  
To develop our new algorithm, it is necessary to define new notions and techniques, which is the purpose of this section. **Proposition 1** ([8]). : _The circulant graph \(C_{n}(s_{1},s_{2},\ldots,s_{k})\) is connected if and only if \(gcd(n,s_{1},s_{2},\ldots,s_{k})=1\)._  
Remark that in Figure 1, the graph \(C_{24}(1,8)\) is connected, while the graph \(C_{24}(4,8)\) is not connected. \begin{table}
\begin{tabular}{c c c} \hline \multicolumn{2}{c}{**Diameter of \(C_{n}(1,s)\)**} \\ \hline \(\gamma=0\) & \(=\lfloor\frac{\lambda+s-1}{2}\rfloor\)[4] \\ \hline \multirow{4}{*}{\(n\) even} & \(s\) odd & \(=\lceil\frac{\lambda}{2}\rceil+\frac{s+1}{2}-\min(\lceil\frac{\gamma}{2} \rceil,\lceil\frac{s-\gamma+1}{2}\rceil)\) \\  & \(s\) even & \(=\begin{cases}\lceil\frac{\lambda}{2}\rceil+\frac{s-\gamma}{2}&\text{if }\gamma \leq 2\lceil\frac{s-2}{4}\rceil,\\ \lfloor\frac{s}{2}\rfloor+\frac{\gamma}{2}&\text{otherwise}.\end{cases}\) \\ \cline{2-3}  & \(n\) odd & \(s\) even & \(=\begin{cases}\lceil\frac{\lambda}{2}\rceil+\frac{s-2}{2}&\text{if }\gamma\in\{1,s-1\},\\ \lfloor\frac{s}{2}\rfloor+\frac{s-\gamma+1}{2}&\text{if }3\leq\gamma\leq 2 \lceil\frac{s}{4}\rceil-1,\\ \lceil\frac{s}{2}\rceil+\frac{\gamma-1}{2}&\text{otherwise}.\end{cases}\) \\ \hline \multirow{4}{*}{\(\lambda>\gamma\)} & \(s\) odd & \(=\begin{cases}p_{1}-1&\text{if }p_{1}=p_{2}\text{ and }p_{4}\equiv 1\pmod{2},\\ e&\text{otherwise}.\end{cases}\) \\  & \(s\) even & \(\leq\min(\max(\lfloor\frac{n}{s}\rfloor+1,n-\lfloor\frac{n}{s}\rfloor s-2,(\lfloor \frac{n}{s}\rfloor+1)s-n-1),\lfloor\frac{n+2}{4}\rfloor,\lfloor\frac{\lfloor \frac{n}{s}\rfloor}{s}\rfloor+\lceil\frac{s}{2}\rceil)\) \\ \hline \end{tabular}
\end{table} 
Table 1: Exact formulas for the diameter of circulant graphs \(C_{n}(1,s)\). **Proposition 2** ([8]). : _All connected circulants are Hamiltonian._  
**Definition 1**. : _A walk is a sequence within a graph that consists of vertices and edges, where both edges and vertices can be revisited. A path, however, is a type of walk where no edges or vertices are repeated._  
**Definition 2**. : _In \(C_{n}(1,s)\), a path from a vertex \(i\) to another vertex \(j\) is denoted as \(P(i,j)\) and is represented as the pair \((\alpha a^{\pm},\beta c^{\pm})\), where:_  
* _The symbol_ \(a\) _(or_ \(c\)_) indicates that_ \(P(i,j)\) _traverses outer (or inner) edges._
* \(\alpha\) _(or_ \(\beta\)_) denotes the number of outer (or inner) edges._
* _The symbol_ \(+\) _(or_ \(-\)_) indicates that_ \(P(i,j)\) _follows the clockwise (or counterclockwise) direction._  
**Remark 1**. : _Let \(i\) and \(j\) be two vertices of \(C_{n}(1,s)\). The path \(P(i,j)\) connecting these vertices can be realized in several ways:_  
1. _The notation_ \(P(i,j)=(\alpha a^{\pm},\beta c^{\pm})\) _represents a path where_ \(P(i,j)\) _moves along_ \(\alpha\) _outer edges either in the clockwise_ \((+)\) _or counterclockwise_ \((-)\) _direction, before continuing through_ \(\beta\) _inner edges either in the clockwise_ \((+)\) _or counterclockwise_ \((-)\) _direction._
2. _The notation_ \(P(i,j)=(\beta c^{\pm},\alpha a^{\pm})\) _represents a path where_ \(P(i,j)\) _traverses_ \(\beta\) _inner edges in the clockwise_ \((+)\) _or counterclockwise_ \((-)\) _direction before proceeding through_ \(\alpha\) _outer edges in the clockwise_ \((+)\) _or counterclockwise_ \((-)\) _direction._
3. _The notation_ \(P(i,j)=(\alpha a^{\pm},0)\) _represents a path where_ \(P(i,j)\) _exclusively traverses_ \(\alpha\) _outer edges in the clockwise_ \((+)\) _or counterclockwise_ \((-)\) _direction._
4. _The notation_ \(P(i,j)=(0,\beta c^{\pm})\) _represents a path where_ \(P(i,j)\) _exclusively traverses_ \(\beta\) _inner edges in the clockwise_ \((+)\) _or counterclockwise_ \((-)\) _direction._  
**Notation 1**. : _Let \(i\) and \(j\) be two vertices of \(C_{n}(1,s)\)._  
1.