Fault Tolerance of Cayley Graphs |
| |
Authors: | Shuhong Gao Beth Novick |
| |
Affiliation: | (1) Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634-0975, USA |
| |
Abstract: | It is a difficult problem in general to decide whether a Cayley graph Cay(G; S) is connected where G is an arbitrary finite group and S a subset of G. For example, testing primitivity of an element in a finite field is a special case of this problem but notoriously hard. In this paper, it is shown that if a Cayley graph Cay(G; S) is known to be connected then its fault tolerance can be determined in polynomial time in |S|log(|G|). This is accomplished by establishing a new structural result for Cayley graphs. This result also yields a simple proof of optimal fault tolerance for an infinite class of Cayley graphs, namely exchange graphs. We also use the proof technique for our structural result to give a new proof of a known result on quasiminimal graphs. Received March 10, 2006 |
| |
Keywords: | KeywordHeading" >: Cayley graph fault tolerance connectivity |
本文献已被 SpringerLink 等数据库收录! |
|