Fixing Numbers of Graphs and Groups

摘要

such that only the trivial automorphism of G fixes every vertex in S. The fixingset of a group F is the set of all fixing numbers of finite graphs with automorphismgroup F. Several authors have studied the distinguishing number of a graph, thesmallest number of labels needed to label G so that the automorphism group of thelabeled graph is trivial. The fixing number can be thought of as a variation of thedistinguishing number in which every label may be used only once, and not everyvertex need be labeled. We characterize the fixing sets of finite abelian groups, andinvestigate the fixing sets of symmetric groups.