Automatically assigned DDC number:

Manually assigned DDC number: 5115

Number of references: 0

Title: A Note on the Asymptotics and Computational Complexity of Graph Distinguishability

Author:

Author:

Subject: Alexander Russell,Ravi Sundaram A Note on the Asymptotics and Computational Complexity of Graph Distinguishability

Description: A graph G is said to be d-distinguishable if there is a d-coloring of G which no non-trivial automorphism preserves. That is, 9c : G ! f1; : : : ; dg; 8f 2 Aut(G)nfidg;9v;c(v) 6= c(f(v)): It was conjectured that if jGj ? jAut(G)j 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) = min f2Aut(G) f6=id j fv 2 G : f(v) 6= vg j; we show that when m(G) ? 2log 2 jAut(G)j, G is indeed 2-distinguishable. In general, we show that if m(G)lnd ? 2ln jAut(G)j 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 f(G;d) : G is d-distinguishableg : We show that this language lies in AM ae S P 2 " P P 2 ....

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1998-04-27

Pubyear: 1998

Format: ps

Identifier: http://citeseer.ist.psu.edu/140547.html

Source: http://webdoc.sub.gwdg.de/edoc/e/EMIS/journals/EJC/Volume_5/PostScriptfiles/v5i1r23.ps

Language: en

Rights: unrestricted