Optimal Graphs for Connectedness under Random Edge Deletion
| dc.contributor.author | Landgren, Lorents | |
| dc.contributor.department | Chalmers tekniska högskola / Institutionen för matematiska vetenskaper | sv |
| dc.contributor.examiner | Steif, Jeffrey | |
| dc.contributor.supervisor | Steif, Jeffrey | |
| dc.date.accessioned | 2021-08-19T12:10:07Z | |
| dc.date.available | 2021-08-19T12:10:07Z | |
| dc.date.issued | 2021 | sv |
| dc.date.submitted | 2020 | |
| dc.description.abstract | 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. | sv |
| dc.identifier.coursecode | MVEX03 | sv |
| dc.identifier.uri | https://hdl.handle.net/20.500.12380/303914 | |
| dc.language.iso | eng | sv |
| dc.setspec.uppsok | PhysicsChemistryMaths | |
| dc.subject | random graph theory, percolation on finite graphs, connected outcome, combinatorics and graph theory, Erdos–Rényi model, stability ordering, optimal graph | sv |
| dc.title | Optimal Graphs for Connectedness under Random Edge Deletion | sv |
| dc.type.degree | Examensarbete för masterexamen | sv |
| dc.type.uppsok | H |