tailieunhanh - Báo cáo toán học: "Identifying Graph Automorphisms Using Determining Sets"

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: Identifying Graph Automorphisms Using Determining Sets. | Identifying Graph Automorphisms Using Determining Sets Debra L. Boutin Department of MATHEmATics HAmiLTON College Clinton NY 13323 dboutin@ Submitted May 31 2006 Accepted Aug 22 2006 Published Sep 7 2006 Mathematics Subject Classification 05C25 Abstract A set of vertices S is a determining set for a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of a graph is the size of a smallest determining set. This paper describes ways of Ending and verifying determining sets gives natural lower bounds on the determining number and shows how to use orbits to investigate determining sets. Further determining sets of Kneser graphs are extensively studied sharp bounds for their determining numbers are provided and all Kneser graphs with determining number 2 3 or 4 are given. 1 Introduction You are a contestant on the newest mathematical game show What s my symmetry The host gives you a graph and an anonymous automorphism Ơ. You are allowed to choose vertices and ask for their images under Ơ. Your goal is to determine the automorphism by correctly identifying the images of the remaining vertices. The amount of money you can win is inversely proportional to the number of vertices whose images you ask to see. In the bonus round you are asked to correctly identify the automorphism group of the graph. The set of vertices you wish to choose is called a determining set and the smallest size of such a set is called the determining number of the graph. As you study in preparation for the game some questions you ask are How can we find a determining set Given a set of vertices how can we decide whether it is determining Can we use Aut G to find a determining set for G Can we use a determining set to find Aut G How small can a determining set be How large might it be What properties of the vertex orbits make it easy to find a determining set or to bound the determining number These questions are addressed in this paper. The .