Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: A Note on the Asymptotics and Computational Complexity of Graph Distinguishability. | A Note on the Asymptotics and Computational Complexity of Graph Distinguishability Alexander Russell acr@ Department of Computer Science University of Texas at Austin AuStin TX 78712 Ravi Sundaram koods@ Delta Global Trading 141 Tremont Street 12th Floor Boston MA 02111 Submitted February 2 1998 Accepted March 24 1998 Abstract A graph G is said to be -distinguishable if there is a d-coloring of G which no non-trivial automorphism preserves. That is 3y G 1 . dg 8Á 2 Aut G idg 9v ỵ v x Á v . It was conjectured that if G Aut G and the Aut G action on G has no singleton orbits then G is 2-distinguishable. We give an example where this fails. We partially repair the conjecture by showing that when enough motion occurs the distinguishing number does indeed decay. Specifically defining m G miiM 1 v 2 G Á v vg peAut G d id we show that when m G 2log2 Aut G G is indeed 2-distinguishable. In general we show that if m G lnd 2ln Aut G then G is d-distinguishable. There has been considerable interest in the computational complexity of the d-distinguishability problem. Specifically there has been much musing on the computational complexity of the language G d G is d-distinguishableg. We show that this language lies in AM c P nP. We use this to conclude that if Dist is coNP-hard then the polynomial hierarchy collapses. AMS Classification Primary 05C25 Secondary 68Q15. the electronic journal of combinatorics 5 1998 R23 2 1 Introduction An undirected graph G is -distinguishable if there is a d coloring of G which no non-trivial automorphism preserves. Formally we write 3y G 1 . d 8Á 2 Aut G id 3v x v X Á v where Aut G denotes the collection of automorphisms of the graph G and id denotes the identity map. One says that such a coloring destroys the symmetries of G. Every graph G is then G -distinguishable and a graph is 1-distinguishable exactly when it is rigid . Aut G 1. The smallest d for which G is d-distinguishable is dubbed the distinguishing .
