Lower bound for degree of sequential diagnosability of Cayley graphs
Toshinori Yamada · 2010
This paper presents that the degree of sequential diagnosability of an N-vertex Cayley graph is Ω(N/D) by generalizing a known technique of finding a lower bound for that of a CCC(cube-connected cycles), where D is the diameter of the Cayley graph. From the lower bound, it is shown that the degrees of sequential diagnosability of the N-vertex star graph and wrapped butterfly are Ω(N log log N/log N) and Ω(N/log N), respectively.