TY - JOUR

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

AU - Shang, Yilun

PY - 2023/4/20

Y1 - 2023/4/20

N2 - 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 → ∞.

AB - 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 → ∞.

KW - Random graphs

KW - Path

KW - Subgraph

KW - Hamiltonian path

U2 - 10.1016/j.ipl.2023.106401

DO - 10.1016/j.ipl.2023.106401

M3 - Article

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

M1 - 106401

ER -