tailieunhanh - Báo cáo toán học: "On the Domination Number of a Random Graph"

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@ Department of Mathematics East Tennessee State University godbolea@ 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 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 .