The infinite motion conjecture for graphs

About 13 years old · traced to

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.

References

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.