zbMATH — the first resource for mathematics

Random subgraphs of the \(n\)-cycle and the \(n\)-wheel. (English) Zbl 0764.05085
Summary: The paper deals with some special types of random graphs, where the initial graphs are paths, cycles, wheels and similar objects. The aim of this paper is to give some characteristics of graphs of that type, such as probability of connectedness, the distribtion of number and size of components, the size of the greatest components and the distribution of degrees of vertices. The case of a finite number of vertices and asymptotic behaviors is considered.

05C80 Random graphs (graph-theoretic aspects)
05C38 Paths and cycles
Full Text: DOI
[1] Barbour, A.D., Poisson convergence and random graphs, Math. proc. Cambridge philos. soc., 92, 349-359, (1982) · Zbl 0498.60016
[2] Barbour, A.D.; Eagleson, G.K., Poisson approximation for some statistics based on exchangeable trials, Adv. in appl. probab., 15, 585-600, (1983) · Zbl 0511.60025
[3] Harary, F., Graph theory, (1971), Addison-Wesley Reading, MA · Zbl 0797.05064
[4] Kordecki, W., Some recurrence formulas for probability of connectedness of random graphs, Theory probab. appl., 30, 3, 630-632, (1985) · Zbl 0595.60015
[5] Lomonosow, M.L., Bernoulli scheme with closure, Problemy peredachi informatsii, 10, 1, 91-100, (1974), [in Russian]
[6] Palka, Z.; Quintas, L.V., Random subgraphs of the n-cycle, Discrete math., 52, 243-251, (1984) · Zbl 0549.05047
[7] Z. Palka and A. Ruciński, Vertex-degree in a random subgraph of a regular graph, Stud. Sci. Math. Hungar., to appear.
[8] Stepanov, V.E., On the probability of connectedness of random graph Gm(t), Theory probab. appl., 15, 1, 55-67, (1970) · Zbl 0233.60006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.