Bipancyclic subgraphs in random bipartite graphs

Abstract

A bipartite graph on 2n vertices is bipancyclic if it contains cycles of all even lengths from 4 to 2n. In this paper we prove that the random bipartite graph $G(n,n,p)$ with $p(n)\gg n^{-2/3}$ asymptotically almost surely has the following resilience property: Every Hamiltonian subgraph $G^{\prime }$ of $G(n,n,p)$ with more than $(1/2+o(1))n^{2}p$ edges is bipancyclic. This result is tight in two ways. First, the range of $p$ is essentially best possible. Second, the proportion 1/2 of edges cannot be reduced. Our result extends a classical theorem of Mitchem and Schmeichel.

14 pages, 3 figures. arXiv admin note: text overlap with arXiv:1005.5716 by other authors

References in corpus (1)

• Local resilience and Hamiltonicity Maker-Breaker games in random-regular graphs

Cited by in corpus (1)

• Cycles in Random Bipartite Graphs