Linearly many faults in Cayley graphs generated by transposition trees
We prove that when linearly many vertices are deleted in a Cayley graph generated by a transposition tree, the resulting graph has a large connected component containing almost all remaining vertices.
cayley graphs transposition tree interconnection networks star graph bubble-sort graph superconnectedness