Please use this identifier to cite or link to this item: https://hdl.handle.net/10593/24948
Title: O strukturze grafów Kroneckera
Other Titles: On the structure of Kronecker graphs
Authors: Banaszak, Justyna
Advisor: Łuczak, Tomasz. Promotor
Keywords: graphs
grafy
combinatorics
kombinatoryka
random structures
struktury losowe
Kronecker graphs
grafy Kroneckera
Issue Date: 2019
Abstract: Przedmiotem pracy jest asymptotyczna struktura grafów Kroneckera. Grafem Kroneckera nazywamy graf, w którym zbiór wierzchołków stanowią wszystkie ciągi binarne o długości n, w którym prawdopodobieństwo, że dwa wierzchołki są połączone krawędzią zależy od liczby pozycji, na których mają one wspólne jedynki, wspólne zera oraz różne wartości. W pracy badam zachowanie grafów Kroneckera przy n dążącym do nieskończoności. W pierwszej części pracy rozważam własności grafów Kroneckera takie jak istnienie skojarzenia doskonałego i δ-krawędziowa spójność, gdzie δ jest minimalnym stopniem grafu. Pokazuję między innymi, że próg dla istnienia skojarzenia doskonałego jest taki sam, jak próg spójności tego grafu. Prezentowane tu wyniki częściowo opierają się na mojej pracy opublikowanej w Electronic Journal of Combinatorics. W ostatnim rozdziale pracy dowodzę, że za progiem spójności grafy Kroneckera mają stałą średnicę z prawdopodobieńśtwem dążącym do 1, gdy n dąży do nieskończoności. Wynik ten pochodzi z mojej wspólnej pracy z Tomaszem Łuczakiem, opublikowanej w Discrete Mathematics.
In the thesis we study the asymptotic structure of Kronecker graphs. Kronecker graph is a graph, where vertex set is the set of all binary vectors of length n, where the probability that two vertices are connected depends on the number of positions in their labels on which they have common zeros, common ones, and different values. In the thesis we study the behaviour of these graphs as n tends to infinity. In the first part of the work we examine several properties of Kronecker graphs such as k-connectivity and the existence of a perfect matching. In particular, we show that the thresholds for connectivity and for the existence of perfect matching basically coincide. These results are partially based on my paper published in Electronic Journal of Combinatorics. In the last chapter of the thesis we study the diameter of Kronecker graphs and prove that just above the connectivity threshold, the diameter of Kronecker graphs, with probability tending to 1 as n tends to infinity, is bounded from above by a constant. The article containing this result, by Tomasz Łuczak and myself, was published in Discrete Mathematics.
Description: Wydział Matematyki i Informatyki
URI: http://hdl.handle.net/10593/24948
Appears in Collections:Doktoraty (WMiI)
Doktoraty 2010-2022 /dostęp otwarty/

Files in This Item:
File Description SizeFormat 
thesis Justyna Banaszak - 2019.pdf475.48 kBAdobe PDFView/Open
Show full item record



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