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

From MaRDI portal





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.




Cited in
(26)








This page was built for publication: Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3147237)