The Distinguishing Index of Infinite Graphs
The Electronic Journal of Combinatorics2015Vol. 22(1)
Citations Over TimeTop 18% of 2015 papers
Abstract
The distinguishing index $D^\prime(G)$ of a graph $G$ is the least cardinal $d$ such that $G$ has an edge colouring with $d$ colours that is only preserved by the trivial automorphism. This is similar to the notion of the distinguishing number $D(G)$ of a graph $G$, which is defined with respect to vertex colourings.We derive several bounds for infinite graphs, in particular, we prove the general bound $D^\prime(G)\leq\Delta(G)$ for an arbitrary infinite graph. Nonetheless, the distinguishing index is at most two for many countable graphs, also for the infinite random graph and for uncountable tree-like graphs.We also investigate the concept of the motion of edges and its relationship with the Infinite Motion Lemma.
Related Papers
- → Separating Models by Formulas and the Number of Countable Models(2012)3 cited
- On the existence of an equilibrium in the Split-the-Difference Mechanism over an uncountable set with a singular part(2006)
- → Proceed with care, because some infinities are larger than others(2020)
- → A new perspective of countable and uncountable infinite sets on Georg Cantor’s definition in set theory(2021)