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 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



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