Large holes in sparse random graphs

DOI10.1007/BF02579303MaRDI QIDQ1113926zbMATH OpenDBLPWikidataFDO

Authors Alan Frieze, Bill Jackson

Publication date 1987

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02579303

zbMATH Keywords

induced cyclesrandom graph evolution

Mathematics Subject Classification ID

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

Review text

Random regular graphs and sparse random graphs with constant average degree are considered, and it is shown that such graphs have large induced cycles with arbitrarily high probability as the order of the graphs tends to infinity.

Recommendations

• The largest hole in sparse random graphs
• On large matchings and cycles in sparse random graphs
• The size of the largest hole in a random graph
• Cycle lengths in sparse random graphs
• Holes in random graphs

Cites work

• Induced trees in sparse random graphs
• Large induced trees in sparse random graphs
• Probability Inequalities for Sums of Bounded Random Variables
• Trees in random graphs

Cited in

(14)

• Large holes in quasi-random graphs
• Maximal induces trees in sparse random graphs
• Holes in random graphs
• On large induced trees and long induced paths in sparse random graphs
• The size of the largest hole in a random graph
• Large induced trees in sparse random graphs
• Depth first exploration of a configuration model
• Many large eigenvalues in sparse graphs
• Implementing Huge Sparse Random Graphs
• Large induced matchings in random graphs
• On Induced Paths, Holes, and Trees in Random Graphs
• Short proofs for long induced paths
• The largest hole in sparse random graphs
• The largest hole in sparse random graphs

This page was built for publication: Large holes in sparse random graphs

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