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
11 February 2003
0 references
0.8716908693313599
0 references
0.8381109237670898
0 references
0.8360112309455872
0 references
0.8356678485870361
0 references
0.8304434418678284
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