tailieunhanh - Báo cáo toán học: "Distinguishing Map"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Distinguishing Maps. | Distinguishing Maps Thomas W. Tucker Department of Mathematics Colgate University Hamilton NY . Submitted Aug 17 2009 Accepted Feb20 2011 Published Feb 28 2011 Mathematics Subject Classification 05E18 05C10 In memory of Michael O. Albertson Abstract The distinguishing number of a group A acting faithfully on a set X denoted D A X is the least number of colors needed to color the elements of X so that no nonidentity element of A preserves the coloring. Given a map M an embedding of a graph in a closed surface with vertex set V and without loops or multiples edges let D M D Aut M V where Aut M is the automorphism group of M if M is orientable define D M similarly using only orientation-preserving automorphisms. It is immediate that D M 4 and D M 3. We use Russell and Sundaram s Motion Lemma to show that there are only finitely many maps M with D M 2. We show that if a group A of automorphisms of a graph G fixes no edges then D A V 2 with five exceptions. That result is used to find the four maps with D M 3. We also consider the distinguishing chromatic number XD M where adjacent vertices get different colors. We show XD M x M 3 with equality in only finitely many cases where x M is the chromatic number of the graph underlying M. We also show that XD M 6 for planar maps answering a question of Collins and Trenk. Finally we discuss the implications for general group actions and give numerous problems for further study. 1 Introduction A group A acting faithfully on a set X has distinguishing number k written D A X k if there is a coloring of the elements of X with k colors such that no nonidentity element of A is color-preserving and no such coloring exists with fewer than k colors. We also say that an action of A on X is k-distinguishable if D A X k. The concept was introduced by Albertson and Collins 2 in the context of the automorphism group of a graph acting on the vertex set and extended to general group actions by Tymoczko 25 see also 4 5 27 . On the other .