Long paths in heterogeneous random subgraphs of graphs with large minimum degree

Yilun Shang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

29 Downloads (Pure)

Abstract

For a graph Gk on n vertices with a minimum degree of at least k → ∞ as n → ∞, let G(n, p) be a random subgraph of Gk taken by retaining each edge (i, j) independently with probability pi j and p = {pi j}(i, j)∈Gk . We show that under certain conditions on the edge probabilities, the resulting random graph has a long path that covers almost all or all vertices with probability tending to 1 as n → ∞.
Original languageEnglish
Article number106401
Number of pages5
JournalInformation Processing Letters
Volume182
Early online date20 Apr 2023
DOIs
Publication statusPublished - 1 Aug 2023

Keywords

  • Combinatorial problems
  • Hamiltonian path
  • Path
  • Random graphs
  • Subgraph

Cite this