

























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ős-Rényi random graph $G_E$ with average edge density $p_n.$ We prove that if $np_n^2 \longrightarrow \infty$ as $n \rightarrow \infty,$ then the longest path contains at least $n-ne^{-δ_1 np_n^2}$ nodes with high probability (i.e., with probability converging to one as $n \rightarrow \infty$), for some constant $δ_1> 0 .$ In particular, if $np_n^2 = M\log{n}$ for some constant $M > 0$ large, then $G_E$ is Hamiltonian with high probability; i.e., the longest path contains all the nodes of $G_E.$ 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.$ If $r_n$ is the connectivity radius and $nr_n^2 \longrightarrow \infty,$ then with high probability, the longest cycle contains at least $n-ne^{-δ_2 nr_n^2}$ nodes for some constant $δ_2 > 0.$ As a consequence of our proof, we obtain that if $nr_n^2 = \log{n} + 7\log{\log{n}} + ω_n$ and $ω_n \longrightarrow \infty$ as $n \rightarrow \infty,$ then with high probability $G_R$ contains a Hamiltonian cycle.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。