Linearly many faults in 2‐tree‐generated networks

Abstract

Abstract In this article we consider a class of Cayley graphs that are generated by certain 3‐cycles on the alternating group A n . These graphs are generalizations of the alternating group graph A G n . We look at the case when the 3‐cycles form a “tree‐like structure,” and analyze its fault resiliency. We present a number of structural theorems and prove that even with linearly many vertices deleted, the remaining graph has a large connected component containing almost all vertices. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010