On the probability that a random subgraph contains a circuit

DOI10.1002/JGT.22095MaRDI QIDQ4978293zbMATH OpenOpenAlexFDO

Authors

Publication date 8 August 2017

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

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

zbMATH Keywords

circuitscycle

Mathematics Subject Classification ID

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

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

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

Cites work

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

Cited in

(3)

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

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)