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 Galpha 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.

Additional Information

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

Source

Harvested from arXiv.org

Creative Commons License

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

Included in

Mathematics Commons

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.