Journal of Combinatorics
Volume 1 (2010)
Distinguishing number and adjacency properties
Pages: 141 – 148
The distinguishing number of countably infinite graphs and relational structures satisfying a simple adjacency property is shown to be 2. This result generalizes both a result of Imrich et al. on the distinguishing number of the infinite random graph, and a result of Laflamme et al. on homogeneous relational structures whose age satisfies the free amalgamation property.
distinguishing number, adjacency property, relational structure, infinite random graph, homogeneous structure
2010 Mathematics Subject Classification
Primary 05C75. Secondary 05C25.