BREAKING SYMMETRY IN COMPLETE GRAPHS BY ORIENTING EDGES - ASYMPTOTIC BOUNDS

We derive upper and lower asymptotic bounds on the minimum number of e dges of K-n that need to be oriented in order to break all its symmetr ies. This number is denoted by io(K-n) in a previous paper by Harary a nd Jacobson. We show that this number is n - Theta (n/lg n). Moreover, our constructive proof leads to a linear-time algorithm that explicit ly achieves this asymptotic optimal bound. We also present an algorith m that, given n, will compute an identity orientation of K-n with leas t number of oriented edges. (C) 1998 Elsevier Science B.V. All rights reserved.