scientific article

zbMath0577.05057MaRDI QIDQ3698835

János Komlós, Miklós Ajtai

Publication date: 1985

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

random graphgraph evolution

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Eulerian and Hamiltonian graphs (05C45)

Related Items (32)

Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs ⋮ Packing Directed Hamilton Cycles Online ⋮ Packing Hamilton Cycles Online ⋮ On the path separation number of graphs ⋮ Crux and Long Cycles in Graphs ⋮ On rainbow Hamilton cycles in random hypergraphs ⋮ Hitting Time of Edge Disjoint Hamilton Cycles in Random Subgraph Processes on Dense Base Graphs ⋮ An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three ⋮ On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three ⋮ The global resilience of Hamiltonicity in \(G(n, p)\) ⋮ Sharp thresholds for half-random games I ⋮ Color‐biased Hamilton cycles in random graphs ⋮ On offset Hamilton cycles in random hypergraphs ⋮ Manipulative Waiters with Probabilistic Intuition ⋮ Finding a Hamilton cycle fast on average using rotations and extensions ⋮ On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs ⋮ Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs ⋮ On the existence of Hamilton cycles with a periodic pattern in a random digraph ⋮ Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs ⋮ Perfect matchings and Hamiltonian cycles in the preferential attachment model ⋮ Optimal covers with Hamilton cycles in random graphs ⋮ On two Hamilton cycle problems in random graphs ⋮ Asymptotically optimal induced universal graphs ⋮ Tight Hamilton cycles in random uniform hypergraphs ⋮ Hamilton cycles in 3-out ⋮ Random graph's Hamiltonicity is strongly tied to its minimum degree ⋮ The threshold for the square of a Hamilton cycle ⋮ Hamiltonicity in random directed graphs is born resilient ⋮ Dirac’s theorem for random regular graphs ⋮ Hamiltonian Berge cycles in random hypergraphs ⋮ Hamiltonicity in random graphs is born resilient ⋮ A hierarchy of randomness for graphs

This page was built for publication: