Directed Scale-Free Graphs And Graph Factors Of Binomial Random Graphs

Random graphs theory is founded by Erdos and Renyi about fifty years ago. As one of the most powerful and widely used tools, it is not only applied in some pure mathematical fields like number theory, combinatorics etc., but also in computer science. Many important results have been obtained on these fields by using the probability method contained in it. Recently the theory has been used for the research of complex networks, including scale-free networks, Ad Hoc networks etc., which makes it receive much attention of combinatorists, probabilists and physicists once again.Based on the previous works, this dissertation studies the modeling of directed scale-free networks and graph factors of the binomial random graphs. Accordingly, its main results are divided into two parts: firstly, a general model of directed scale-free graphs and a model of directed scale free graphs with random multi-edges deletion are established, and the in- and out-degree of both models are proved to follow power laws. Directed scale-free graphs defined in this dissertation can be used to model some large-scale real-world networks like World Wide Web/Internet and they will be more nature and appropriate models in some way than others. Secondly, while graphs asymptotically almost surely have (no) some kind of graph factor, an upper (and lower) bound of the parameter p of binomial random graphs is discovered. The whole thesis consists of four chapters as follows:Chapter one contains a brief introduction to current development, application of random graphs.The aim of. chapter two is to present the definitions and inequalities that we shall need in the main body of the thesis.Directed scale-free graphs are studied in chapter three. A general model of directed scale-free graph process which grows with random multi-edges is defined in section two, while a graph process that grows with random multi-edges deletion is defined in section three. The in- and out-degrees of both models are proved to obey power laws. Compared with other models, random multi-edges growth or deletion steps are added in the graph processes.Chapter four is concerned about classical random graph. Prerequisites are presented in section one and two. As binomial random graphs asymptotically almost surely have (no) some kind of graph factors, an upper (and lower) bound of its parameter p is obtained in section three. The difference of this work from others is that the graph factors here is not fixed.