Sharp thresholds for Hamiltonicity in random intersection graphs

DOI10.1016/j.tcs.2010.06.022zbMath1205.05210OpenAlexW2086721908MaRDI QIDQ708225

Charilaos Efthymiou, Paul G. Spirakis

Publication date: 11 October 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.06.022

zbMATH Keywords

sharp thresholdHamilton cyclesrandom intersection graphstochastic order relation between \(G_{n, p}\) and \(G_{n,m,p}\)

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)

Related Items

On the Hamiltonicity of random bipartite graphs, On Some Combinatorial Properties of Random Intersection Graphs, The largest component in critical random intersection graphs, Recent advances on the Hamiltonian problem: survey III, On the chromatic number of non-sparse random intersection graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Expander properties and the cover time of random intersection graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Expander Properties and the Cover Time of Random Intersection Graphs
• On Random Intersection Graphs: The Subgraph Problem
• The degree sequence of a random graph. I. The models
• The vertex degree distribution of random intersection graphs
• Tail bounds for occupancy and the satisfiability threshold conjecture
• Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models
• Sharp Threshold for Hamiltonicity of Random Geometric Graphs
• Automata, Languages and Programming
• Automata, Languages and Programming
• Sur deux propriétés des classes d'ensembles
• Algorithms and Computation