Long Paths and Hamiltonian paths in Inhomogenous Random Graphs

In this paper, we study long paths and Hamiltonian paths in inhomogenous random graphs. In the first part of the paper, we consider an inhomogenous Erd\H{o}s-R'enyi random graph $G_E$ with average edge density $p_n\mathrm{.}$ We prove that if $n{p}_n^2⟶\mathrm{\infty }$ as $n\to \mathrm{\infty },$ then the longest path contains at least $n-n{e}^{-{\delta }_{1}n{p}_n^2}$ nodes with high probability (i.e., with probability converging to one as $n \rightarrow \infty$),forsomeconstant$\delta_1> 0 .$Inparticular,if$np_n^2 = M\log{n}$forsomeconstant$M > 0$large,then$G_E$ is Hamiltonian with high probability; i.e., the longest path contains all the nodes of $G_E\mathrm{.}$ In the second part of the paper, we consider a random geometric graph $G_R$ consisting of $n$ nodes, each independently distributed according to a (not necessarily uniform) density $f\mathrm{.}$ If $r_n$ is the connectivity radius and $n{r}_n^2⟶\mathrm{\infty },$ then with high probability, the longest cycle contains at least $n-n{e}^{-{\delta }_{2}n{r}_n^2}$ nodes for some constant $\delta_2 > 0.$Asaconsequenceofourproof,weobtainthatif$nr_n^2 = \log{n} + 7\log{\log{n}} + \omega_n$and$\omega_n \longrightarrow \infty$as$n \rightarrow \infty,$thenwithhighprobability$G_R$ contains a Hamiltonian cycle.