This thesis deals with random graph processes. More precisely it deals with two random graph processes which create H -free graphs. The first of these processes is the random H-elimination process which starts from the complete graph and in every step removes an edge uniformly at random from the set of edges which are found in a copy of H. The second is the H-free random graph process which starts from the empty graph and in every step an edge chosen uniformly at random from the set of edges which when added to the graph would not create a copy of H is inserted. We consider these graph processes for several classes of graphs H, for example strictly two balanced graphs. The class of strictly two balanced graphs includes among others cycles and complete graphs. We analysed the H-elimination process, when H is strictly 2-balanced. For this class we show the typical number of edges found at the end of the process. We also consider the sub graphs created by the process and its independence number. We also managed to show the expected number of edges in the H -elimination pro- cess when H = Ki, the graph created from the complete graph on 4 vertices by removing an edge and when H = K34 where K34 is created from the complete bi- partite graph with 3 vertices in one partition and'4 vertices in the second partition, by removing an edge. In case of the H -free process we considered the case when H is the triangle and showed that the triangle-free random graph process only creates sparse subgraphs. Finally we have improved the lower bound on the length of the K34-free random graph process. '
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:580620 |
| Date | January 2012 |
| Creators | Makai, Tamas |
| Contributors | Gerke, Stefanie |
| Publisher | Royal Holloway, University of London |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://repository.royalholloway.ac.uk/items/b24b89af-3fc1-4d2f-a673-64483a3bc2f2/8/ |
Page generated in 0.0017 seconds