Imrich, Wilfried, Lehner, Florian and Smith, Simon (2020) Distinguishing density and the Distinct Spheres Condition. European Journal of Combinatorics, 89 . p. 103139. ISSN 01956698
Full content URL: https://doi.org/10.1016/j.ejc.2020.103139
Documents 


PDF
density_sub4_vAccepted.pdf  Whole Document 310kB 
Item Type:  Article 

Item Status:  Live Archive 
Abstract
If a graph G has distinguishing number 2, then there exists a partition of its vertex set into two parts, such that no nontrivial automorphism of G fixes setwise the two parts. Such a partition is called a 2distinguishing coloring of G, and the parts are called its color classes. If G admits such a coloring, it is often possible to find another in which one of the color classes is sparse in a certain sense. In this case we say that G has 2distinguishing density zero. An extreme example of this would be an infinite graph admitting a 2distinguishing coloring in which one of the color classes is finite.
The Infinite Motion Conjecture is a wellknown open conjecture about 2distinguishability. A graph G is said to have infinite motion if every nontrivial automorphism of G moves infinitely many vertices, and the conjecture states that every connected, locally finite graph with infinite motion is 2distinguishable. In this paper we show that for many classes of graphs for which the Infinite Motion Conjecture is known to hold, the graphs have 2distinguishing density zero.
Keywords:  Distinguishing number, Symmetry breaking 

Subjects:  G Mathematical and Computer Sciences > G100 Mathematics G Mathematical and Computer Sciences > G110 Pure Mathematics 
Divisions:  College of Science > School of Mathematics and Physics 
ID Code:  40541 
Deposited On:  09 Apr 2020 11:03 
Repository Staff Only: item control page