论文标题
计算循环图中距离和直径的新方法
A new approach for computing the distance and the diameter in circulant graphs
论文作者
论文摘要
图的直径是所有对顶点之间的最大距离。因此，如果任何两个顶点在距离最多$ d $，并且距离$ d $有两个顶点，则图$ g $具有直径$ d $。我们有兴趣研究循环图的直径$ c_n（1，s）$，即用$ \ {0,1，\ ldots，n-1 \} $作为顶点集的$ \ {0,1，\ ldots，n-1 \} $作为vertex集，并且两个不同的vertices $ i，j \ in \ in \ in \ in \ in \ in \ in \ wif {0, dect＆n; $ | i-j | _n \ in \ {1，s \} $，其中$ 2 \ leq s \ leq \ leq \ lfloor \ frac {n-1} {2} {2} \ rfloor $和$ | x | x | _n = \ min（| x |，n- | x |）$。尽管循环图有规律性，但很难评估几个参数，尤其是距离和直径。据我们所知，没有公式为所有$ n $和$ s $的距离和直径提供精确值。在这种情况下，我们在本文中介绍了一种基于简单算法的新方法，该算法为循环图的距离和直径提供了精确的值。
The diameter of a graph is the maximum distance among all pairs of vertices. Thus a graph $G$ has diameter $d$ if any two vertices are at distance at most $d$ and there are two vertices at distance $d$. We are interested in studying the diameter of circulant graphs $C_n(1,s)$, i.e., graphs with the set $\{0,1,\ldots, n-1\}$ of integers as vertex set and in which two distinct vertices $i,j \in \{0,1,\ldots, n-1\}$ are adjacent if and only if $|i-j|_n\in \{1,s\}$, where $2\leq s\leq \lfloor \frac{n-1}{2} \rfloor$ and $|x|_n=\min(|x|, n-|x|)$. Despite the regularity of circulant graphs, it is difficult to evaluate several parameters, in particular the distance and the diameter. To the best of our knowledge, there is no formulas providing exact values for the distance and the diameter of $C_n(1,s)$ for all $n$ and $s$. In this context, we present in this paper a new approach, based on a simple algorithm, that gives exact values for the distance and the diameter of circulant graphs.
