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 language | English |
---|---|
Article number | 106401 |
Number of pages | 5 |
Journal | Information Processing Letters |
Volume | 182 |
Early online date | 20 Apr 2023 |
DOIs | |
Publication status | Published - 1 Aug 2023 |
Keywords
- Combinatorial problems
- Hamiltonian path
- Path
- Random graphs
- Subgraph