×

zbMATH — the first resource for mathematics

On the diameter and bisector size of Cayley graphs. (English) Zbl 0778.05038
Lower bounds on the diameter of Cayley graphs of groups with nilpotent subgroups, and upper bounds of the size of node bisectors of Cayley graphs of groups with solvable subgroups are proved. Some applications of these results to the theory of interconnection networks are discussed.

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX Cite
Full Text: DOI
References:
[1] M. Ajtai, J. Komlós, and E. Szemerédi (1983): Sorting inc logn parallel steps.Combinatorica 3, 1-19. · Zbl 0523.68048
[2] S. B. Akers and B. Krishnamurthy (1987): The fault tolerance of star graphs.Proc. 2nd Internat. Conf. on Supercomputing, pp. 270-276. · Zbl 0641.94049
[3] S. B. Akers and B. Krishnamurthy (1989): A group-theoretic model for symmetric interconnection networks.IEEE Trans. Comput. 38, 555-566. · Zbl 0678.94026
[4] F. Annexstein, M. Baumslag, and A. L. Rosenberg (1990): Group-action graphs and parallel architectures.SIAM J. Comput. 19(3), 544-569. · Zbl 0698.68064
[5] L. Babai (1991): Local expansion of vertex transitive graphs and random generation in finite groups.Proc. 23rd ACM Symp. on Theory of Computing, pp. 164-174.
[6] L. Babai, G. Hetyei, W. M. Kantor, A. Lubotsky and A. Seress (1990): On the diameter of finite groups.Proc. 31st IEEE Symp. on Foundations of Computer Science, pp. 857-865.
[7] L. Babai, W. M. Kantor, and A. Lubotsky (1989): Small diameter cayley graphs for finite simple groups.European J. Combin. 10(6), 507-522. · Zbl 0702.05042
[8] H. Bass (1972): The degree of polynomial growth for finitely generated nilpotent groups.Proc. London Math. Soc. 25, 603-614. · Zbl 0259.20045
[9] M. Baumslag and A. L. Rosenberg (1991): Processor-time tradeoffs for cayley graph interconnection networks.Proc. 6th Distributed Memory Computing Conf., pp. 630-636.
[10] L. Campbell, G. E. Carlsson, V. Faber, M. R. Fellows, M. A. Langston, J. W. Moore, A. P. Mullhaupt, and H. B. Sexton (1988): Dense symmetric networks from linear groups and codes. Computer Science Technical Report CS-88-192, Washington State University.
[11] G. E. Carlsson, J. E. Cruthirds, H. B. Sexton, and C. G. Wright (1985): Interconnection networks based on a generalization of cube-connected cycles.IEEE Trans. Comput. 34, 769-772. · Zbl 0572.94019
[12] G. E. Carlsson, M. R. Fellows, H. B. Sexton, and C. G. Wright (1988): Group theory as an organizing principle in parallel processing.J. Combin. Theory Combin. Comput. 3.
[13] R. N. Draper (1991): An overview of supertoroidal networks.Proc. 3rd ACM Symp. on Parallel Algorithms and Architectures, pp. 95-102.
[14] V. Faber (1989): Global communication algorithms for hypercubes and other Cayley coset graphs.SIAM J. Discrete Math.
[15] P. Feldman, J. Friedman, and N. Pippenger (1988): Wide-sense nonblocking networks.SIAM J. Discrete Math. 1(2), 158-173. · Zbl 0648.94025
[16] O. Gabber and Z. Galil (1981): Explicit constructions of linear-sized superconcentrators.J. Comput. System Sci. 22, 407-420. · Zbl 0487.05045
[17] F. P. Greenleaf (1969):Invariant Means on Topological Groups, Van Nostrand, New York. · Zbl 0174.19001
[18] M. Gromov (1981): Groups of polynomial growth and expanding maps.Publ. Math. IHES 53, 53-78. · Zbl 0474.20018
[19] M. Hall, Jr. (1976):Theory of Groups. Chelsea, New York.
[20] M. Klawe (1984): Limitations on explicit constructions of expanding graphs.SIAM J. Comput. 13(1), 156-166. · Zbl 0537.68068
[21] F. T. Leighton and B. Maggs (1989): Expanders might be practical: fast algorithms for routing around faults on multibutterflies.Proc. 30th IEEE Symp. on Foundations of Computer Science, pp. 384-389.
[22] A. Lubotsky (1990): Discrete Groups, Expanding Graphs, and Invariant Measures. Unpublished manuscript.
[23] A. Lubotsky, R. Phillips, and P. Sarnak (1988): Ramanujan graphs.Combinatorica 8(3), 261-277. · Zbl 0661.05035
[24] G. Margulis (1975): Explicit constructions of concentrators.Problemy Peredachi Informatisii 9(4), 71-80(Problems Inform. Transmission,10, 325-332).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.