2013/01/03 by Florian Lehner, Lehner, Florian
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1301.0393
arxiv created 2013/01/08 · arxiv updated 2013/01/09
A graph G is said to be 2-distinguishable if there is a 2-labeling of its vertices which is not preserved by any nontrivial automorphism of G. We show that every locally finite graph with infinite motion and growth at most O(2^((1-ε) √(n)/2)) is 2-distinguishable. Infinite motion means that every automorphism moves infinitely many vertices and growth refers to the cardinality of balls of radius n.