Optimal Graphs for Connectedness under Random Edge Deletion
Typ
Examensarbete för masterexamen
Program
Publicerad
2021
Författare
Landgren, Lorents
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
Performing percolation on a finite graph G means independently keeping or
discarding each edge according to a probability parameter p. The focus is the
probability Pc(G, p) that a percolation outcome turns out to be a connected
graph. Specifically, if we fix p, the number of vertices n and the number of edges
m, we try to find the graph(s) with the highest such probability. We call such
graphs the most stable or the (n, m, p)-optimal graphs. It is shown that any
(n, m, p)-optimal graph consists of a single so-called block.
For m = n, m = n + 1 and m = n + 2 respectively, we show the existence
of a unique optimal graph, which is actually independent of p. However, in
general, the relative stability of two (n,m)-graphs is p-dependent. We make
some investigations into when this is the case.
Beskrivning
Ämne/nyckelord
random graph theory, percolation on finite graphs, connected outcome, combinatorics and graph theory, Erdos–Rényi model, stability ordering, optimal graph