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: Distinguishability of Locally Finite Trees. | Distinguishability of Locally Finite Trees Mark E. Watkins Department of Mathematics Syracuse University Syracuse NY 13244-1150 mewatkin@ Xiangqian Zhou Department of Mathematics University of Mississippi Oxford Ms 38677-9701 xzhou@ Submitted Mar 30 2006 Accepted Mar 28 2007 Published Apr 4 2007 Abstract The distinguishing number A X of a graph X is the least positive integer n for which there exists a function f V X 0 1 2 n 1g such that no nonidentity element of Aut X fixes setwise every inverse image f_ 1 k k 2 0 1 2 n 1g. All infinite locally finite trees without pendant vertices are shown to be 2-distinguishable. A proof is indicated that extends 2-distinguishability to locally countable trees without pendant vertices. It is shown that every infinite locally finite tree T with finite distinguishing number contains a finite subtree J such that A J A T . Analogous results are obtained for the distinguishing chromatic number namely the least positive integer n such that the function f is also a proper vertex-coloring. 1 Introduction The distinguishing number A X of a graph X is the least positive integer n for which there exists a function f V X 0 1 2 n 1g such that every element of Aut X fails to fix setwise at least one of the inverse images f_1 k k 2 0 1 2 n 1g. Intuitively A X is the least number of colors with which V X can be colored so that no automorphism preserves all of the color classes. We call X n-distinguishable if A X n. The notion of distinguishability is originally due to Albertson and Collins 1 and has been pursued in 6 . THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 R29 1 The distinguishing chromatic number of a graph G was proposed by Collins and Trenk 3 . Denoted by Xa G it is the least positive integer n for which there exists a function f V G 0 1 n 1g such that in addition to the above condition also satisfies the condition that for all u v 2 V G f u f v whenever u and v are adjacent. The purpose of this paper is to .
