tailieunhanh - Báo cáo toán học: "Fixing Numbers of Graphs and Groups"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Fixing Numbers of Graphs and Groups. | Fixing Numbers of Graphs and Groups Courtney R. Gibbons University of Nebraska - Lincoln Department of Mathematics 228 Avery Hall PO Box 880130 Lincoln NE 68588-0130 s-cgibbon5@ Joshua D. Laison Mathematics Department Willamette University 900 State St. Salem OR 97301 jlaison@ Submitted Sep 11 2006 Accepted Mar 12 2009 Published Mar 20 2009 Mathematics Subject Classification 05C25 Abstract The fixing number of a graph G is the smallest cardinality of a set of vertices S such that only the trivial automorphism of G fixes every vertex in S. The fixing set of a group r is the set of all fixing numbers of finite graphs with automorphism group r. Several authors have studied the distinguishing number of a graph the smallest number of labels needed to label G so that the automorphism group of the labeled graph is trivial. The fixing number can be thought of as a variation of the distinguishing number in which every label may be used only once and not every vertex need be labeled. We characterize the fixing sets of finite abelian groups and investigate the fixing sets of symmetric groups. 1 Introduction In this paper we investigate breaking the symmetries of a finite graph G by labeling its vertices. There are two standard techniques to do this. The first is to label all of the vertices of G with k distinct labels. A labeling is distinguishing if no nontrivial automorphism of G preserves the vertex labels. The distinguishing number of G is the minimum number of labels used in any distinguishing labeling 1 13 . The distinguishing chromatic number of G is the minimum number of labels used in any distinguishing labeling which is also a proper coloring of G 6 . The second technique is to label a subset of k vertices of G with k distinct labels. The remaining labels can be thought of as having the null label. We say that a labeling of G is fixing if no non-trivial automorphism of G preserves the vertex labels and the fixing number of G is the minimum