Random subgraphs of the n-cycle
type: Item
instance of: scholarly article
title: Random subgraphs of the n-cycle
zbMATH Open document ID: 0549.05047
DOI: 10.1016/0012-365X(84)90085-2
author: Louis V. Quintas
author: Zbigniew Palka
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 3875331
zbMATH Keywords: cycle
zbMATH Keywords: random subgraph
zbMATH Keywords: asymptotic behaviour
reviewed by: Klaus Schürger
MaRDI profile type: Publication
cites work: Q3041240
cites work: Vertices of given degree in a random graph
cites work: Q5545069
cites work: Q3267900
cites work: Q3286850
cites work: A review of random graphs
cites work: On the number of vertices of given degree in a random graph
cites work: On the degrees of vertices in a bichromatic random graph
full work available at URL: 0012-365x(84)90085-2
OpenAlex ID: W1980134326
description: scientific article; zbMATH DE number 3875331