Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-25T17:41:28.106Z Has data issue: false hasContentIssue false
  • English
  • Français

On Subgraph Sizes in Random Graphs

Published online by Cambridge University Press:  12 September 2008

Neil Calkin ,
Alan Frieze  and
Brendan D. McKay
Neil Calkin
Affiliation:
Department of Mathematics, Carnegie Mellon University, Pittsburgh, U.S.A.
Alan Frieze
Affiliation:
Department of Mathematics, Carnegie Mellon University, Pittsburgh, U.S.A.
Brendan D. McKay
Affiliation:
Department of Computer Science, Australian National University, Canberra, Australia
Get access Rights & Permissions [Opens in a new window]

Abstract

For a graph G with m edges let its Range of Subgraph Sizes (RSS)

ρ(G) = {t : G contains a vertex-induced subgraph with t edges}.

G has a full RSS if ρ(G) = {0, 1, …, m}. We establish the threshold for a random graph to have a full RSS and give tight bounds on the likely RSS of a dense random graph.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 1 , Issue 2 , June 1992 , pp. 123 - 134
Copyright
Copyright © Cambridge University Press 1992

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

[1]Bollobás, B. (1985) Random Graphs. Academic Press, London.Google Scholar
[2]Knuth, D. E., Mothwani, R. and Pittel, B. (1990) Stable husbands. Random Structures and Algorithms 1, 1–14.Google Scholar