tailieunhanh - Báo cáo toán học: "Distinguishing numbers for graphs and groups"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Distinguishing numbers for graphs and groups. | Distinguishing numbers for graphs and groups Julianna Tymoczko Department of Mathematics University of Michigan Ann Arbor MI 48109 tymoczko@ Submitted Jan 30 2004 Accepted Aug 25 2004 Published Sep 16 2004 2000 MR Subject Classification 05C15 05C25 20D60 Abstract A graph G is distinguished if its vertices are labelled by a map ộ V G 1 2 . k so that no non-trivial graph automorphism preserves ộ. The distinguishing number of G is the minimum number k necessary for ộ to distinguish the graph. It measures the symmetry of the graph. We extend these definitions to an arbitrary group action of r on a set X. A labelling ộ X 1 2 . k is distinguishing if no element of r preserves ộ except those which fix each element of X. The distinguishing number of the group action on X is the minimum k needed for ộ to distinguish the group action. We show that distinguishing group actions is a more general problem than distinguishing graphs. We completely characterize actions of Sn on a set with distinguishing number n answering an open question of Albertson and Collins. 1 Introduction Consider the following dilemma of the considerate roommate. Returning home late at night she would like to unlock her door without disturbing her roommates either by turning on a light or by repeatedly trying incorrect keys in the lock. One solution is to put different handles on her keys so that no matter how her keychain is oriented she can identify each key simply by its shape and its order on the chain. This leads to a natural question what is the minimum number of handles needed to tell her keys apart Motivated by this puzzle Albertson and Collins defined a distinguished graph to be one whose vertices are labelled by a function ộ V G 1 . k so that no non-trivial Part of this research was done at the Summer Research Program at the University of Minnesota Duluth sponsored by the National Science Foundation DMS-9225045 and the National Security Agency MDA904-91-H-0036 . THE ELECTRONIC JOURNAL OF