Mathematics – Combinatorics
Scientific paper
2011-06-23
Mathematics
Combinatorics
Scientific paper
The {\em 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 {\em distinguishing number} of a graph is the distinguishing number of its full automorphism group acting on its vertex set. A connected graph $\Gamma$ is said to have {\em 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 {\em 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.
Smith Simon M.
Tucker Thomas W.
Watkins Mark E.
No associations
LandOfFree
Distinguishability of infinite groups and graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Distinguishability of infinite groups and graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distinguishability of infinite groups and graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-470434