Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-26T01:11:12.944Z Has data issue: false hasContentIssue false
  • English
  • Français

Some remarks about extreme degrees in a random graph

Published online by Cambridge University Press:  24 October 2008

Zbigniew Palka
Zbigniew Palka
Affiliation:
Institute of Mathematics, A. Mickiewicz University, Poznań, Poland
Get access Rights & Permissions [Opens in a new window]

Extract

Let Kn, p be a random subgraph of a complete graph Kn obtained by removing edges, each with the same probability q = 1 – p, independently of all other edges (i.e. each edge remains in Kn, p with probability p). Very detailed results devoted to probability distributions of the number of vertices of a given degree, as well as of the extreme degrees of Kn, p, have already been obtained by many authors (see e.g. [l]–[5], [7]–[9]). A similar subject for other models of random graphs has been investigated in [10]–[13], The aim of this note is to give some supplementary information about the distribution of the ith smallest (i ≥ 1 is fixed) and the ith largest degree in a sparse random graph Kn, p, i.e. when p = p(n) = o(1).

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 100 , Issue 1 , July 1986 , pp. 167 - 174
Copyright
Copyright © Cambridge Philosophical Society 1986

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Bollobás, B.. The distribution of the maximum degree of a random graph. Discrete Math. 32 (1980), 201–203.CrossRefGoogle Scholar
[2]Bollobás, B.. Degree sequences of random graphs. Discrete Math. 33 (1981), 1–19.CrossRefGoogle Scholar
[3]Bollobás, B.. Vertices of given degree in a random graph. J. Graph Theory 6 (1982), 147–155.CrossRefGoogle Scholar
[4]Cornuéjols, G.. Degree sequences of random graphs. (To appear.)Google Scholar
[5]Erdös, P. and Rényi, A.. On the strength of connectedness of a random graph. Ada Math. Acad. Sci. Hungar. 12 (1961), 261–267.CrossRefGoogle Scholar
[6]Feller, W.. An Introduction to Probability Theory and its Applications, vol. 1 (Wiley, 1968).Google Scholar
[7]Grimmett, G. and McDiarmid, C.. On colouring random graphs. Math. Proc. Cambridge Philos. Soc. 77 (1975), 313–324.CrossRefGoogle Scholar
[8]Ivchenko, G.. On the asymptotic behaviour of degrees of vertices in a random graph. Theory Probab. Appl. 18 (1973), 188–196.CrossRefGoogle Scholar
[9]Palka, Z.. On the number of vertices of given degree in a random graph. J. Graph Theory 8 (1984), 167–170.CrossRefGoogle Scholar
[10]Palka, Z.. On the degrees of vertices in a bichromatic random graph. Period. Math. Hungar. 15 (1984), 121–126.CrossRefGoogle Scholar
[11]Palka, Z.. Extreme degrees in random subgraphs of regular graphs. Math. Proc. Cambridge Philos. Soc. 97 (1985), 69–78.CrossRefGoogle Scholar
[12]Palka, Z.. Extreme degrees in random graphs. J. Graph Theory (in the press).Google Scholar
[13]Palka, Z. and Ruciński, A.. Vertex-degrees in a random subgraph of a regular graph. (To appear.)Google Scholar