Lower bound for degree of sequential diagnosability of Cayley graphs

摘要

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/logN) and Ω(N/logN), respectively.