
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.
primitive permutation group, Graph operations (line graphs, products, etc.), Group Theory (math.GR), Enumeration in graph theory, 510, Coloring of graphs and hypergraphs, FOS: Mathematics, Mathematics - Combinatorics, Infinite automorphism groups, distinguishing number, Cartesian product of graphs, distinct spheres condition, G110 - Pure mathematics, 004, Graphs and abstract algebra (groups, rings, fields, etc.), Primitive groups, Infinite graphs, primitive graph, Combinatorics (math.CO), 05E18, 05C15, infinite motion, Mathematics - Group Theory, Mathematics
primitive permutation group, Graph operations (line graphs, products, etc.), Group Theory (math.GR), Enumeration in graph theory, 510, Coloring of graphs and hypergraphs, FOS: Mathematics, Mathematics - Combinatorics, Infinite automorphism groups, distinguishing number, Cartesian product of graphs, distinct spheres condition, G110 - Pure mathematics, 004, Graphs and abstract algebra (groups, rings, fields, etc.), Primitive groups, Infinite graphs, primitive graph, Combinatorics (math.CO), 05E18, 05C15, infinite motion, Mathematics - Group Theory, Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 15 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
