Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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í toán học quốc tế đề tài: On the Domination Number of a Random Graph. | On the Domination Number of a Random Graph Ben Wieland Anant P. Godbole Department of Mathematics University of Chicago wieland@math.uchicago.edu Department of Mathematics East Tennessee State University godbolea@etsu.edu Submitted May 2 2001 Accepted October 11 2001. MR Subject Classifications 05C80 05C69 Abstract In this paper we show that the domination number D of a random graph enjoys as sharp a concentration as does its chromatic number ỵ. We first prove this fact for the sequence of graphs G n pn n 1 where a two point concentration is obtained with high probability for pn p fixed or for a sequence pn that approaches zero sufficiently slowly. We then consider the infinite graph Gfâ p where p is fixed and prove a three point concentration for the domination number with probability one. The main results are proved using the second moment method together with the Borel Cantelli lemma. 1 Introduction A set Y of vertices of a graph G V E constitutes a dominating set if each v 2 V is either in Y or is adjacent to a vertex in Y. The domination number D of G is the size of a dominating set of smallest cardinality. Domination has been the subject of extensive research see for example Section 1.2 in 1 or the texts 6 7 . In a recent Rutgers University dissertation Dreyer 3 examines the question of domination for random graphs motivated by questions in search structures for protein sequence libraries. Recall that the random graph G n rp is an ensemble of n vertices with each of the potential n edges being inserted independently with probability p where p often approaches zero as n 1. The treatises of Bollobás 2 and Janson et al. 8 between them cover the theory of random graphs in admirable detail. Dreyer 3 generalizes some results of Nikoletseas and Spirakis 5 and proves that with q 1 1 p p fixed and for any 0 any fixed set of cardinality 1 logợ n is a dominating set with probability approaching unity as n 1 and that sets of size 1 logạ n dominate with probability .
