Name
Abstract | ||
|---|---|---|
A graph G is said to be 2-distinguishable if there is a labeling of the vertices with two labels such that only the trivial automorphism preserves the labels. Call the minimum size of a label class in such a labeling of G the cost of 2-distinguishing G. Within the class of connected, locally finite, infinite graphs, we show that those with finite 2-distinguishing cost are precisely the graphs with countable automorphism group. Further we show that, for such graphs, the cost is less than three times the size of a smallest determining set (a set which only the trivial automorphism fixes pointwise). Finally we show that graphs with linear growth rate c have the even smaller upper bound of c + 1 on their cost of 2-distinguishing. |
Year | Venue | Keywords |
|---|---|---|
2014 | ELECTRONIC JOURNAL OF COMBINATORICS | Distinguishing number,Distinguishability,Automorphism,Determining set,Determining number,Infinite graph |
Field | DocType | Volume |
Graph automorphism,Discrete mathematics,Graph,Combinatorics,Indifference graph,Countable set,Vertex (geometry),Automorphism,Chordal graph,Mathematics,Maximal independent set | Journal | 21.0 |
Issue | ISSN | Citations |
4.0 | 1077-8926 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Debra L. Boutin | 1 | 61 | 8.77 |
| W. Imrich | 2 | 64 | 20.65 |