Journal of Combinatorics

Volume 1 (2010)

Number 2

Distinguishing number and adjacency properties

Pages: 141 – 148

DOI: http://dx.doi.org/10.4310/JOC.2010.v1.n2.a4

Authors

Anthony Bonato (Department of Mathematics, Ryerson University, Toronto, Ontario, Canada)

Dejan Delic (Department of Mathematics, Ryerson University, Toronto, Ontario, Canada)

Abstract

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.

Keywords

distinguishing number, adjacency property, relational structure, infinite random graph, homogeneous structure

2010 Mathematics Subject Classification

Primary 05C75. Secondary 05C25.

Full Text (PDF format)