Distinguishing infinite graphs (Q2372880)

Summary: The distinguishing number \(D(G)\) of a graph \(G\) is the least cardinal number \(\aleph\) such that \(G\) has a labeling with \(\aleph\) labels that is only preserved by the trivial automorphism. We show that the distinguishing number of the countable random graph is two, that tree-like graphs with no more than continuum many vertices have distinguishing number two, and determine the distinguishing number of many classes of infinite Cartesian products. For instance, \(D(Q_{\mathfrak n}) = 2\), where \(Q_{\mathfrak n}\) is the infinite hypercube of dimension \({\mathfrak n}\).