Random subgraphs of the n-cycle (Q800378): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Zbigniew Palka / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Klaus Schürger / rank | |||
Normal rank |
Revision as of 03:39, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Random subgraphs of the n-cycle |
scientific article |
Statements
Random subgraphs of the n-cycle (English)
0 references
1984
0 references
Let \(C_ n\) denote the undirected n-cycle with vertices \(v_ 1,...,v_ n\) and edges \(\{v_ 1,v_ 2\}\), \(\{v_ 2,v_ 3),...,\{v_ n,v_ 1\}\). Let \(RC_ n(p)\) (0\(\leq p\leq 1)\) denote the random subgraph of \(C_ n\), having the same vertices as \(C_ n\) and being such that each edge of \(C_ n\) is selected or rejected with probability p or 1-p, respectively (different edges being treated independently). The authors investigate e.g. the asymptotic behaviour (as \(n\to\infty \)) of \(X_ 0(n)\) (the number of isolated vertices of \(RC_ n(p))\) and M(n) (the number of isolated vertices of \(RC_ n(p))\) and M(n) (the order of the largest connected component of \(RC_ n(p))\). It is shown, e.g., that if \(p=1-w(n)/\sqrt{n}\), \((x_ 0(n)-w^ 2(n)/w(n)\) asymptotically has a standard normal distribution.
0 references
cycle
0 references
random subgraph
0 references
asymptotic behaviour
0 references