The infinite motion conjecture for graphs

Let GG be an infinite, locally finite, connected graph. Write Aut(G)\operatorname{Aut}(G) for its automorphism group, m(G)\operatorname{m}(G) for its motion, and D(G)\operatorname{D}(G) for its distinguishing number.

Infinite motion conjecture for graphs. If Aut(G)\operatorname{Aut}(G) has infinite motion, then

D(G)=2.\operatorname{D}(G)=2.

Automorphism groups of connected, locally finite graphs are closed and subdegree-finite, so this conjecture follows from the corresponding permutation-group conjecture. It is known for several growth ranges, including super-linear subquadratic growth and superpolynomial subexponential growth, but remains open for general locally finite connected graphs.

Sources & referencesView supporting material

Primary source

Wilfried Imrich, Simon M. Smith, Thomas W. Tucker and Mark E. Watkins, “Infinite Motion and 2-Distinguishability of Graphs and Groups”, arXiv:1304.6436 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.