Name
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 automorphism group acting on its vertex set. A connected graph Gamma is said to have connectivity 1 if there exists a vertex alpha is an element of V Gamma such that Gamma \ {alpha} is not connected. For alpha is an element of 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 |
Year | Venue | Keywords |
|---|---|---|
2012 | ELECTRONIC JOURNAL OF COMBINATORICS | distinguishing number,primitive permutation group,primitive graph,Distinct Spheres Condition,infinite motion,Cartesian product of graphs |
Field | DocType | Volume |
Graph automorphism,Discrete mathematics,Combinatorics,Graph toughness,Infinite group,Line graph,Cartesian product of graphs,Cycle graph,Symmetric graph,Universal graph,Mathematics | Journal | 19.0 |
Issue | ISSN | Citations |
2.0 | 1077-8926 | 8 |
PageRank | References | Authors |
1.21 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Simon M. Smith | 1 | 8 | 1.21 |
| Thomas W. Tucker | 2 | 191 | 130.07 |
| Mark E. Watkins | 3 | 109 | 32.53 |