Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-10T17:30:58.112Z Has data issue: false hasContentIssue false
  • English
  • Français

Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity

Published online by Cambridge University Press:  12 July 2002

COLIN COOPER ,
ALAN FRIEZE  and
BRUCE REED
COLIN COOPER
Affiliation:
Department of Mathematical and Computing Sciences, Goldsmiths College, University of London, New Cross, London SE14 6NW, UK (e-mail: c.cooper@gold.ac.uk)
ALAN FRIEZE
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA15213, USA (e-mail: alan@random.math.cmu.edu)
BRUCE REED
Affiliation:
Equipe Combinatoire, CNRS, Université e de Paris VI, 4 Place Jussieu, Paris 75005, France (e-mail: reed@ecp6.jussieu.fr)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let Gr denote a graph chosen uniformly at random from the set of r-regular graphs with vertex set {1,2, …, n}, where 3 [les ] r [les ] c0n for some small constant c0. We prove that, with probability tending to 1 as n → ∞, Gr is r-connected and Hamiltonian.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 11 , Issue 3 , May 2002 , pp. 249 - 261
Copyright
2002 Cambridge University Press