Infinite graphs with finite 2-distinguishing cost (Q490268)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Infinite graphs with finite 2-distinguishing cost |
scientific article |
Statements
Infinite graphs with finite 2-distinguishing cost (English)
0 references
22 January 2015
0 references
Summary: 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\). We show that the connected, locally finite, infinite graphs with finite 2-distinguishing cost are exactly the graphs with countable automorphism group. Further we show that in such graphs the cost is less than three times the size of a smallest determining set. We also another, sharper bound on the 2-distinguishing cost, in particular for graphs of linear growth.
0 references
distinguishing number
0 references
distinguishability
0 references
automorphism
0 references
determining set
0 references
determining number
0 references