Please use this identifier to cite or link to this item: http://hdl.handle.net/10593/10873
Title: Własności losowych nakryć grafów
Other Titles: Properties of random coverings of graphs
Authors: Witkowski, Marcin
Advisor: Łuczak, Tomasz
Keywords: Grafy
Graphs
Grafy losowe
Random Graphs
Nakrycia grafów
Graph Coverings
Cykle Hamiltona
Hamilton Cycles
Spójność grafów
Graph Connectivity
Issue Date: 30-May-2014
Abstract: Przedmiotem rozprawy doktorskiej są asymptotyczne własności losowych nakryć grafów zdefiniowanych przez Amita i Liniala w 2002 roku, jako nowy model grafu losowego. Dla zadanego grafu bazowego G losowe nakrycie stopnia n, oznaczane jako Ḡ, otrzymujemy poprzez zastąpienie każdego wierzchołka v przez n-elementowy zbiór Ḡ_v oraz wybór, dla każdej krawędzi e={x,y} \in E(G), z jednostajnym prawdopodobieństwem, losowego skojarzenia pomiędzy zbiorami Ḡ_x i Ḡ_y. Pierwszym zagadnieniem poruszanym w pracy jest oszacowanie wielkości największej topologicznej kliki zawartej (jako podgraf) w losowym nakryciu danego grafu G. Udało się pokazać, że asymptotycznie prawie na pewno losowe nakrycie grafu G zawiera największą z możliwych topologiczną klikę. Drugim badanym zagadnieniem jest pytanie o istnienie w podniesieniu grafu cyklu Hamiltona. W pracy pokazujemy, że jeżeli graf G zawiera dwa krawędziowo rozłączne cykle Hamiltona, których suma nie jest grafem dwudzielnym i ma minimalny stopień co najmniej 5, to asymptotycznie prawie na pewno nakrycie Ḡ jest grafem hamiltonowskim.
In the thesis we study selected properties of random coverings of graphs introduced by Amit and Linial in 2002. A random n-covering of a graph G, denoted by Ḡ, is obtained by replacing each vertex v of G by an n-element set Ḡ_v and then choosing, independently for every edge e = {x,y}\in E(G), uniformly at random a perfect matching between Ḡ_x and Ḡ_y. The first problem we consider is the typical size of the largest topological clique in random covering of given graph G. We show that asymptotically almost surely a random n-covering of a graph G contains the largest possible topological clique. The second property we examine is the existence of a Hamilton cycle in Ḡ. We show that if G contains two edge disjoint Hamilton cycles, which sum is not a bipartite graph and has minimum degree at least 5, then asymptotically almost surely Ḡ is Hamiltonian.
Description: Wydział Matematyki i Informatyki
URI: http://hdl.handle.net/10593/10873
Appears in Collections:Doktoraty 2010-2016 /dostęp otwarty/
Doktoraty (WMiI)

Files in This Item:
File Description SizeFormat 
Properties of random coverings of graphs-Marcin Witkowski.pdf789.83 kBAdobe PDFView/Open
Show full item record



Items in AMUR are protected by copyright, with all rights reserved, unless otherwise indicated.