On the probability that a random subgraph contains a circuit

DOI10.1002/JGT.22095zbMATH Open1367.05196arXiv1502.05009OpenAlexW2963199049MaRDI QIDQ4978293FDOQ4978293

Authors:

Publication date: 8 August 2017

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: Let $mu>2$ and $epsilon>0$. We show that, if $G$ is a sufficiently large simple graph of average degree at least $mu$, and $H$ is a random spanning subgraph of $G$ formed by including each edge independently with probability $pgefrac1mu-1+epsilon$, then $H$ contains a cycle with probability at least $1-epsilon$.

Full work available at URL: https://arxiv.org/abs/1502.05009

Recommendations

• The threshold probability for long cycles
• Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs
• scientific article; zbMATH DE number 4110728
• Long cycles in random subgraphs of graphs with large minimum degree
• scientific article; zbMATH DE number 3916307

zbMATH Keywords

cyclecircuits

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38)

Cites Work

• Probability. Theory and examples.
• Random walks and percolation on trees
• The Moore bound for irregular graphs
• Title not available (Why is that?)
• Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs
• On the non-planarity of a random subgraph
• On the Error-Correcting Capabilities of Cycle Codes of Graphs
• The Maximum-Likelihood Decoding Threshold for Cycle Codes of Graphs
• Regular graphs whose subgraphs tend to be acyclic

Cited In (3)

• On the cycle space of a random graph
• On the non-planarity of a random subgraph
• The largest component in a random subgraph of the \(n\)-cycle

This page was built for publication: On the probability that a random subgraph contains a circuit

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