Distinguishing Infinite Graphs

Citations Over TimeTop 16% of 2007 papers

Abstract

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 not 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_{n}) = 2$, where $Q_{n}$ is the infinite hypercube of dimension ${n}$.

Related Papers

• → Martin’s Axiom is consistent with the existence of nowhere trivial automorphisms(2001)20 cited
• → On a question of Silver about gap-two cardinal transfer principles(2017)
• → On a question of Silver about gap-two cardinal transfer principles(2017)
• → Unthreadability with Small Conditions(2022)