Y Shang. On the hamiltonicity of random bipartite graphs
Submitted on: Mar 08, 2013, 18:49:50
Natural Sciences / Mathematics / Combinatorics
Description: We prove that if $pggln n/n$, then a.a.s. every subgraph of random bipartite graph $G(n,n,p)$ with minimum degree at least $(1/2+o(1))np$ is Hamiltonian. The range of $p$ and the constant $1/2$ involved are both asymptotically best possible. The result can be viewed as a generalization of the Dirac theorem within the context of bipartite graphs. The proof uses P'osa's rotation and extension method and is closely related to a recent work of Lee and Sudakov.
The Library of Congress (USA) reference page : http://lccn.loc.gov/cn2013300046.
To read the article posted on Intellectual Archive web site please click the link below.
on the hamiltonicity of random bipartite graphs.pdf