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 abstract of this article has been published in the "Intellectual Archive Bulletin" , September 2013, ISSN 1929-1329.
The Library and Archives Canada reference page: collectionscanada.gc.ca/ourl/res.php?url_ver=Z39.88......
To read the article posted on Intellectual Archive web site please click the link below.
on the hamiltonicity of random bipartite graphs.pdf