Infinite graphs with finite 2-distinguishing cost
The electronic journal of combinatorics, Tome 21 (2014) no. 4
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.
DOI :
10.37236/4263
Classification :
05C63, 05C40, 05C60
Mots-clés : distinguishing number, distinguishability, automorphism, determining set, determining number
Mots-clés : distinguishing number, distinguishability, automorphism, determining set, determining number
@article{10_37236_4263,
author = {Debra Boutin and Wilfried Imrich},
title = {Infinite graphs with finite 2-distinguishing cost},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {4},
doi = {10.37236/4263},
zbl = {1305.05163},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4263/}
}
Debra Boutin; Wilfried Imrich. Infinite graphs with finite 2-distinguishing cost. The electronic journal of combinatorics, Tome 21 (2014) no. 4. doi: 10.37236/4263
Cité par Sources :