Bipancyclic subgraphs in random bipartite graphs

arXiv1211.6766MaRDI QIDQ6237575FDOQ6237575

Authors: Yilun Shang 

Publication date: 28 November 2012

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.

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

This page was built for publication: Bipancyclic subgraphs in random bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6237575)