Can I read Breaking Symmetry in Complete Graphs by Orienting Edges: Asymptotic Bounds on EtoBox?

Breaking Symmetry in Complete Graphs by Orienting Edges: Asymptotic Bounds by Frank Harary; Desh Ranjan is a scholarly article available to read on EtoBox.

What is Breaking Symmetry in Complete Graphs by Orienting Edges: Asymptotic Bounds about?

We derive upper and lower asymptotic bounds on the minimum number of edges of K,, that need to be oriented in order to break all its symmetries. This number is denoted by ia in a previous paper by Harary and Jacobson. We show that this number is n -O(n/lgn). Moreover, our constructive proof leads to a linear-time algorithm that explicitly achieves this asymptotic optimal bound. We also present an algorithm that, given n, will compute an identity orientation of Kn with least number of oriented edges.

Author

Frank Harary; Desh Ranjan

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0020-0190)

Published

1998

Language

EN