2018/01/08 by Wilfried Imrich, Florian Lehner, Imrich, Wilfried +3
Mathematics · #03E10 #05C15 #05C25 #05C63 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:03E10 #msc:05C15 #msc:05C25 #msc:05C63
paper · pdf · doi:10.48550/arxiv.1801.02405
arxiv created 2018/01/08 · arxiv updated 2018/01/09
If a graph G has distinguishing number 2, then there exists a partition of its vertex set into two parts, such that no nontrivial automorphism of G fixes setwise the two parts. Such a partition is called a 2-distinguishing coloring of G, and the parts are called its color classes. If G admits such a coloring, it is often possible to find another in which one of the color classes is sparse in a certain sense. In this case we say that G has 2-distinguishing density zero. An extreme example of this would be an infinite graph admitting a 2-distinguishing coloring in which one of the color classes is finite. If a graph G contains a vertex v such that, for all n ∈ \mathbb N, any two distinct vertices equidistant from v have nonequal n-spheres, then we say that G satisfies the Distinct Spheres Condition. In this paper we prove a general result: any countable connected graph that satisfies the Distinct Spheres Condition is 2-distinguishable with density zero. We present two proofs of this, one that uses a deterministic coloring, and another (that applies only to locally finite graphs) using a random coloring. From this result, we deduce that several important families of countably infinite and connected graphs are 2-distinguishable with density zero, including those that are locally finite and primitive. Furthermore, we prove that any connected graph with infinite motion and subquadratic growth is 2-distinguishable with density zero.