Fault Tolerance of Cayley Graphs

Shuhong Gao and Beth Novick

Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634-
0975, USA

{sgao, nbeth}@ces.clemson.edu

Annals of Combinatorics 11 (2) p.161-171 June, 2007

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.

References:

1. S. Akers and B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput. 38 (4) (1989) 555-566.

2. B. Alspach, Cayley graphs with optimal fault tolerance, IEEE Trans. Comput. 41 (10) (1992) 1337–1339.

3. L. Babai, W.M. Kantor, and A. Lubotzky, Small diameter Cayley graphs for finite simple groups, Europ. J. Combin. 10 (1989) 507-522.

4. W.W. Boone, F.B. Cannonito, and R.L. Lyndon,Word Problems: Decision Problem in Group Theory, North-Holland Publishing Co., Netherlands, 1973.

5. A. Cayley, On the theory of groups, Proc. London Math. Soc. 9 (1878) 126–233.

6. S. Even, Graph Algorithms, Computer Science Press, Inc., Woodland Hills, Calif, 1979.

7. T. Feder and R. Motwani, Clique partitions, graph compression and speeding-up algorithms, J. Comput. System Sci. 51 (1995) 261–272.

8. H.N. Gabow and T. Jordán, Incrementing bipartite digraph edge-connectivity, J. Comb. Optim. 4 (2000) 449–486.

9. S. Gao, B. Novick, and K. Qiu, From Hall's matching theorem to optimal routing on hypercubes, J. Combin. Theory Ser. B 74 (1998) 291–301.

10. S. Gao and D.F. Hsu, Short containers in Cayley graphs, DIMACS Tech. Rep. 2001-18, available at http://www.math.clemson.edu/%7Esgao/pub.html.

11. C. Godsil, Connectivity of minimal Cayley graphs, Arch. Math. (Basel) 37 (1981) 473–476.

12. C. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, Vol. 207, Springer-Verlag, New York, 2001.

13. Y.O. Hamidoune, Sur les atomes d'un graph orienté, C. R. Acad. Sci. Paris Ser. I 284 (20) (1977) 1253–1256.

14. Y.O. Hamidoune, On the connectivity of Cayley digraphs, Europ. J. Combin. 5 (1984) 309– 312.

15. Y.O. Hamidoune, A.S. Lladó, and O. Serra, The connectivity of hierarchical Cayley digraphs, Discrete Appl. Math. 37/38 (1992) 275–280.

16. Y.O. Hamidoune, A.S. Lladó, and O. Serra, Small cutsets in quasiminimal Cayley graphs, Discrete Math. 159 (1996) 131–142.

17. P.-S. Loh and L.J. Schulman, Improved expansion of random Cayley graphs, Discrete Math. Theoret. Comput. Sci. 6 (2004) 523–528.

18. A. Lubotzky, Cayley graphs: eigenvalues, expanders and random walks, In: Survey in Combinatorics, P. Rowlinson Ed., Cambridge University Press, Cambridge, (1995) pp. 155–189.

19. J. Morris, Connectivity of Cayley graphs: a special family, J. Combin. Math. Combin. Comput. 20 (1996) 111–120.

20. P.S. Novikov, On the algorithmic unsolvability of the word problem in group theory, Trudy Mat. Inst. im. Steklov, No. 44, Izdat. Akad. Nauk SSSR, Moscow, (1955) 143 pp.

21. S.T. Schibell and R.M. Stafford, Processor interconnection networks from Cayley graphs, Discrete Math. 40 (1992) 333–357.

22. M. Watkins, Connectivity of transitive graphs, J. Combin. Theory 8 (1970) 23–29.