Fast algorithm of calculating diameter for Bi-Cayley graph with 4 degrees on cyclic group
Zhong We · Computer Engineering and Applications Journal · 2015
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).