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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Random Threshold Graphs Elizabeth Perez Reilly Edward R. Scheinerman. | Random Threshold Graphs Elizabeth Perez Reilly Edward R. Scheinerman Department of Applied Mathematics and Statistics Johns Hopkins University Baltimore Maryland 21218 USA. Submitted Feb 3 2009 Accepted Oct 13 2009 Published Oct 31 2009 Mathematics Subject Classifications 05C62 05C80 Abstract We introduce a pair of natural equivalent models for random threshold graphs and use these models to deduce a variety of properties of random threshold graphs. Specifically a random threshold graph G is generated by choosing n IID values x1 . xn uniformly in 0 1 distinct vertices i j of G are adjacent exactly when Xị Xj 1. We examine various properties of random threshold graphs such as chromatic number algebraic connectivity and the existence of Hamiltonian cycles and perfect matchings. 1 Introduction and Overview of Results Threshold graphs were introduced by Chvatal and Hammer in 4 5 see also 6 13 . There are several logically equivalent ways to define this family of graphs but the one we choose works well for developing a model of random graphs. A simple graph G is a threshold graph if we can assign weights to the vertices such that a pair of distinct vertices is adjacent exactly when the sum of their assigned weights is or exceeds a specified threshold. Without loss of generality the threshold can be taken to be 1 and the weights can be restricted to lie in the interval 0 1 see Definition . References 2 9 16 provide an extensive introduction to this class of graphs. If we choose the weights for the vertices at random we induce a probability measure on the set of threshold graphs and thereby create a notion of a random threshold graph. Given that we may assume the weights lie in 0 1 it is natural to take the weights independently and uniformly in that interval a careful definition is given in . The idea of choosing a random representation has been explored in other contexts such as random geometric graphs 18 choose points in a metric space at random to represent .