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

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1802785
Language Label Description Also known as
default for all languages
No label defined
    English
    Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
    scientific article; zbMATH DE number 1802785

      Statements

      Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity (English)
      0 references
      0 references
      0 references
      0 references
      11 February 2003
      0 references
      This paper deals with random \(r\)-regular graphs. Let \(G_r\) denote a graph selected uniformly at random from the set of \(r\)-regular graphs with vertex set \(\{1,2,3,\dots,n\}\). The following is the main result of this paper: There is a small positive absolute constant \(c_0\) with \(3\leq r\leq c_0n\) such that with probability \(\to 1\) as \(n\to\infty\), we have (a) \(G_r\) is \(r\)-connected, and (b) \(G_r\) is Hamiltonian. The ``edge switching techniques'' have been extensively employed in this paper.
      0 references

      Identifiers