Distinguishability of infinite groups and graphs

Simon M Smith¹ ; Thomas W Tucker² ; Mark E Watkins¹

¹Syracuse University
²Colgate University

The electronic journal of combinatorics, Tome 19 (2012) no. 2

Résumé

The distinguishing number of a group $G$ acting faithfully on a set $V$ is the least number of colors needed to color the elements of $V$ so that no non-identity element of the group preserves the coloring. The distinguishing number of a graph is the distinguishing number of its automorphism group acting on its vertex set. A connected graph $\Gamma$ is said to have connectivity 1 if there exists a vertex $\alpha \in V\Gamma$ such that $\Gamma \setminus \{\alpha\}$ is not connected. For $\alpha \in V$, an orbit of the point stabilizer $G_\alpha$ is called a suborbit of $G$.We prove that every nonnull, primitive graph with infinite diameter and countably many vertices has distinguishing number $2$. Consequently, any nonnull, infinite, primitive, locally finite graph is $2$-distinguishable; so, too, is any infinite primitive permutation group with finite suborbits. We also show that all denumerable vertex-transitive graphs of connectivity 1 and all Cartesian products of connected denumerable graphs of infinite diameter have distinguishing number $2$. All of our results follow directly from a versatile lemma which we call The Distinct Spheres Lemma.

Détail

DOI : 10.37236/2283

Classification : 05C15, 05C76, 05C30, 20B15, 20B27, 05C63, 05C25
Mots-clés : distinguishing number, primitive permutation group, primitive graph, distinct spheres condition, infinite motion, Cartesian product of graphs