Premium
Linearly many faults in 2‐tree‐generated networks
Author(s) -
Cheng Eddie,
Lipták László,
Sala Fred
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20319
Subject(s) - combinatorics , cayley graph , graph , mathematics , class (philosophy) , computer science , discrete mathematics , artificial intelligence
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