Random induced graphs (Q1598829)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Random induced graphs |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Random induced graphs |
scientific article |
Statements
Random induced graphs (English)
0 references
28 May 2002
0 references
A property \(P\) of graphs is monotone if, whenever a graph \(G\) has \(P\), so does every subgraph of \(G\). Given a graph \(H\), the random induced graph \(G_{1/2}(H)\) is obtained by selecting vertices of \(H\) independently, with probability \(1/2\), and taking the subgraph of \(H\) induced by the selected vertex set. The authors are interested in the general question of how large \(d(n)\) should be to ensure that, for a given monotone property \(Q\), if \((H_n)\) is any sequence of graphs such that \(H_n\) has \(n\) vertices and minimum degree at least \(d(n)\), then almost every \(G_{1/2}(H_n)\) has property \(Q\). They prove essentially best-possible results when \(Q\) is the property that the graph is \(k\)-connected and when \(Q\) is the property that the graph is Hamiltonian showing that, in latter case, one can take \(d(n)\) to be \(n/2 + (2n\log n)^{1/2}\).
0 references
monotone property
0 references