On randomk-out subgraphs of large graphs

DOI10.1002/rsa.20650zbMath1359.05068arXiv1405.2129OpenAlexW1902987962MaRDI QIDQ2977562

Tony Johansson, Alan M. Frieze

Publication date: 18 April 2017

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1405.2129

zbMATH Keywords

Hamilton cyclerandom subgraph\(k\)-out

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (5)

Hitting Time of Edge Disjoint Hamilton Cycles in Random Subgraph Processes on Dense Base Graphs ⋮ Perfect fractional matchings in \(k\)-out hypergraphs ⋮ Connectivity of the k-Out Hypercube ⋮ Unnamed Item ⋮ On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs

Cites Work

• On the connectivity of random m-orientable graphs and digraphs
• Maximum matchings in a class of random graphs
• Matchings in random regular bipartite digraphs
• One-factor in random graphs based on vertex choice
• On the Expected Value of a Random Assignment Problem
• Hamilton cycles in 3-out
• Optimal Packings of Hamilton Cycles in Sparse Random Graphs
• Long paths and cycles in random subgraphs of graphs with large minimum degree
• Probability Inequalities for Sums of Bounded Random Variables
• On the Non-Planarity of a Random Subgraph
• Robust Hamiltonicity of Dirac graphs
• Expanders via Random Spanning Trees

This page was built for publication: On randomk-out subgraphs of large graphs