In this paper, we introduce a new measure of symmetry which we call the symmetry ratio of a network, defined to be the ratio of the number of distinct eigenvalues of the network to D+1, where D is the diameter. The symmetry ratio has utility in partially predicting the robustness of a network in the face of attack. We prove a number of results placing bounds on the symmetry ratio for several families of networks, including distance-transitive networks, prisms, twisted prisms, antiprisms, tori, Cayley graphs, and random graphs.
|Cite as: Dekker, A.H. and Colbert, B. (2005). The Symmetry Ratio of a Network. In Proc. Eleventh Computing: The Australasian Theory Symposium (CATS2005), Newcastle, Australia. CRPIT, 41. Atkinson, M. and Dehne, F., Eds. ACS. 13-20. |