# A New Algorithm for Computing the Distance and the Diameter in Circulant Graphs
## 1 Introduction  
Given \(n\geq 5\), \(D=\{1,2,\ldots,\lfloor\frac{n}{2}\rfloor\}\), and a generating set \(S\subseteq D\), the circulant graph \(C_{n}(S)\) has \(\{0,1,\ldots,n-1\}\) as a vertex set and in which two distinct vertices \(i\) and \(j\) are adjacent if and only if \(|i-j|_{n}\in S\), where \(|x|_{n}=\min(|x|,n-|x|)\) is the circular distance modulo \(n\). We can use \(C_{n}(\{s_{1},s_{2},\ldots,s_{k}\})\), or simply \(C_{n}(s_{1},s_{2},\ldots,s_{k})\), to denote the circulant graph on \(n\) vertices, with respect to the connection set \(S=\{s_{1},s_{2},\ldots,s_{k}\}\), where \(1\leq s_{1}<s_{2}<\ldots<s_{k}\leq\lfloor\frac{n}{2}\rfloor\). Remark that \(C_{n}(1)\) is the cycle \(C_{n}\), while \(C_{n}(D)\) is the complete graph \(K_{n}\). For example, the circulant graphs \(C_{24}(4,8)\) and \(C_{24}(1,8)\) are illustrated in Figure 1.  
The diameter of circulant graphs has been the subject of various investigations, with both theoretical and algorithmic contributions. [PERSON] and [PERSON] [1] analyzed theasymptotic behavior of diameters in random circulant graphs, showing they scale as \(n^{1/k}\) for 2k-regular graphs. [PERSON] (2000) explored the degree-diameter problem for circulant graphs of degrees 10 and 11, while [PERSON] et al. [PERSON] et al. (2016) proposed constructions for large circulant graphs with fixed diameter and arbitrary degree. Previous studies have produced theoretical bounds, both upper and lower, (see ([PERSON] et al., 2016; [PERSON] et al., 2016)). In terms of algorithms, [PERSON] and [PERSON] were pioneers in presenting the problem and suggested a heuristic algorithm to tackle it [PERSON] and [PERSON] (2016). Moreover, [PERSON] and [PERSON] delved into this topic and devised an algorithm to calculate the diameter of \(C_{n}(1,s)\) with a runtime complexity of \(O(\log(n))\)[PERSON] and [PERSON] (2016). Our primary goal isn't just to develop an algorithm for computing the diameter for a given circulant graph. Instead, we aim to derive a new algorithm that calculates the diameter without the need to implement the graph itself, optimizing both space and time efficiency. Another key objective is for this new algorithm to provide theoretical formulas for the distance and diameter of any circulant graph. This is crucial, as having such formulas significantly contributes to several key areas, including graph labeling and packing coloring. Moreover, they enhance the traceability of circulant graphs and provide precise formulas for their upper traceable numbers. Other parameters that depend on the diameter can also have their formulas determined. However, this undertaking comes with significant challenges. Despite the regular structure and vertex-transitivity of circulant graphs, even a slight alteration, like changing the graph's order, completely transforms the graph, affecting the values of distance and diameter. This complexity highlights the intricate nature of analyzing circulant graphs and emphasizes the difficulties in deriving theoretical formulas for their distance and diameter. [PERSON] and [PERSON] demonstrated in [PERSON] and [PERSON] (2016) that circulant graphs with different generating sets can still be isomorphic, indicating that it is unnecessary to study the diameter of all circulant graphs individually. Moreover, the cardinality of \(S\) inversely affects the diameter of the circulant graph \(C_{n}(S)\): a larger cardinality of \(S\) results in a smaller diameter. For instance, \(C_{n}(D)\) is isomorphic to the complete graph \(K_{n}\) with an order of \(n\) and a diameter of 1. If \(S=D\setminus X\), where \(|X|=1\) or \(|X|=2\), then \(diam(C_{n}(S))=2\)[PERSON] and [PERSON] (2016). Therefore, it is both challenging and crucial to study circulant graphs with generators \(S\) of smaller cardinality, for instance \(|S|=2\). However, for any circulant graph \(C_{n}(S)\) with generator \(S=\{s_{1},s_{2}\}\) satisfying \(gcd(n,s_{1})=1\) or \(gcd(n,s_{2})=1\), \(C_{n}(S)\) is isomorphic to \(C_{n}(1,s)\) (see Theorem 1).