FAULT RESILIENCY OF CAYLEY GRAPHS GENERATED BY TRANSPOSITIONS
Eddie Cheng, László Lipták · International Journal of Foundations of Computer Science · 2007
The star graph Sn, proposed by [1], has many advantages over the n-cube. It is shown in [2] that when a large number of vertices are deleted from Sn, the resulting graph can have at most two components, one of which is small. In this paper, we show that Cayley graphs generated by transpositions have this property.