#### Document Type

Article

#### Date

6-23-2011

#### Embargo Period

11-18-2011

#### Disciplines

Mathematics

#### Description/Abstract

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 full automorphism group acting on its vertex set. A connected graph T is said to have connectivity 1 if there exists a vertex alpha in VT such that T \ {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 connected primitive graph with infinite diameter and countably many vertices has distinguishing number 2. Consequently, any infinite, connected, primitive, locally finite graph is 2-distinguishable; so, too, is any infinite primitive 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.

#### Recommended Citation

Smith, Simon M.; Tucker, Thomas W.; and Watkins, Mark E., "Distinguishability of Infinite Groups and Graphs" (2011). *Mathematics Faculty Scholarship*. 111.

https://surface.syr.edu/mat/111

#### Source

Harvested from arXiv.org

#### Creative Commons License

This work is licensed under a Creative Commons Attribution 3.0 License.

## Additional Information

This manuscript is from arXiv.org, for more information see http://arxiv.org/abs/1106.4778