Y Shang. On the hamiltonicity of random bipartite graphs


Natural Sciences / Mathematics / Combinatorics

Submitted on: Mar 08, 2013, 18:49:50

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



© 2011-2017 Shiny World Corp. All rights reserved. To reach us please send an e-mail to support@IntellectualArchive.com