计算循环群上4度Bi-Cayley网络直径的快速算法

Fast algorithm of calculating diameter for Bi-Cayley graph with 4 degrees on cyclic group

Cayley图是一类高对称正则图,有许多好性质,被广泛认为是一类理想的互连网络拓扑结构。Bi-Cayley图是Cayley图的一个自然推广,特别地,循环群上4度Bi-Cayley网络BC(n;±s1,±s2)是双环网络DLG(n;±s1,±s2)的一个自然推广。讨论了循环群n上4度Bi-Cayley网络BC(n;±s1,±s2)连通的充分必要条件,并给出了计算该网络直径的一种算法,其时间复杂度为O(lb n)。

Cayley graph is a kind of high symmetrical regular graph, has many good properties, is widely regarded as a kind of ideal interconnection network topology. Bi-Cayley graph is a natural promotion of Cayley graph, in particular,Bi-Cayley graph BC（n; ±s1, ±s2） with 4 degrees on the cyclic group is a natural extension of double loop network DLG（n; ±s1, ±s2）. This paper discusses the sufficient and necessary conditions of the graph BC（n; ±s1, ±s2） connectivity and gives an algorithm to compute the diameter of BC（n; ±s1, ±s2）, its time complexity is O（lb n）.