tailieunhanh - Báo cáo toán học: "On Computing the Distinguishing Numbers of Trees and Forests"

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: On Computing the Distinguishing Numbers of Trees and Forests. | On Computing the Distinguishing Numbers of Trees and Forests Christine T. Cheng Department of Computer Science University of Wisconsin-Milwaukee Milwaukee WI 53211 USA. ccheng@ Submitted Apr 28 2005 Accepted Jan 18 2006 Published Feb 8 2006 Mathematics Subject Classification 05C 68R 68W Abstract Let G be a graph. A vertex labeling of G is distinguishing if the only label-preserving automorphism of G is the identity map. The distinguishing number of G D G is the minimum number of labels needed so that G has a distinguishing labeling. In this paper we present O n log n -time algorithms that compute the distinguishing numbers of trees and forests. Unlike most of the previous work in this area our algorithm relies on the combinatorial properties of trees rather than their automorphism groups to compute for their distinguishing numbers. 1 Introduction The notion of distinguishing numbers came about because of the following recreational problem of Rubin s 11 suppose a professor has a set of n keys on a circular key ring that are indistinguishable to the naked eye. To tell them apart he attaches a colored marker on each key. What is the fewest number of colored markers needed so he can distinguish the keys from each other The answer is quite surprising - it is 3 when n 2 3 4 5 but drops down to 2 when n 6. The answer is dependent on the fact that the keyholder was circular. If for example the keys were suspended from a straight rod then it is not hard to see that two colors suffice for all n 2. This observation motivated Albertson and Collins 2 to generalize the original problem to arbitrary graphs. The vertices of a graph represented the keys and its edges indicate how the keys are connected to each other hence the keys on a circular key ring corresponded to Cn while the keys on a straight rod correspondeded to Pn. They asked the following question given a graph G what is the minimum number of colors needed to distinguish the vertices from each other They .