Parsimonious Asymmetrization of Graphs

A coloring of the vertex set of a graph g is distinguishing or asymmetrizing if the identity automorphism is the only automorphism that preserves it. the minimum number of colors needed for adistinguishing coloring is the distinguishing number d(g). for graphs g with distinguishing number 2the vertex set v (g) can be partitioned into two sets, each of which is only preserved by the identityautomorphism. such sets are called asymmetrizing and the minimum cardinality of such a set is the2-distinguishing cost ρ(g) of g. for infinite graphs ρ(g) may be infinite. in that case one looks forsparse asymmetrizing sets and defines a 2-distinguishing density. closely related to these parametersis the motion m(g) of a graph g. it is the minimum number of vertices moved by each nonidentityautomorphism.the talk treats the relationship between these parameters in general and in more detail for certainclasses of graphs. in particular, we consider trees of arbitrary cardinalities, compact trees, graphs ofmaximum valence 3, and vertex transitive cubic graphs.on the way we construct cubic vertex transitive graphs with finite motion and positive distinguishingdensity. the finite versions of such graphs turn out to be split praeger{xu graphs, for which we thusprovide another characterization