The motion conjecture for graphs

About 13 years old · traced to

Let GG be an infinite graph of arbitrary cardinality. Write m⁡(G)\operatorname{m}(G) for its motion, Aut⁡(G)\operatorname{Aut}(G) for its automorphism group, and D⁡(G)\operatorname{D}(G) for its distinguishing number.

Motion conjecture for graphs. The inequality

2m⁡(G)≥∣Aut⁡(G)∣2^{\operatorname{m}(G)}\geq |\operatorname{Aut}(G)|

implies

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

This is the infinite-cardinality form of the Motion Conjecture for Graphs and would extend the Motion Lemma beyond finite automorphism groups. The source presents it as a conjecture and gives no resolution in the stated generality.

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.