On the independence number and Hamiltonicity of uniform random intersection graphs

DOI10.1016/j.tcs.2011.09.003zbMath1233.05186OpenAlexW2014672313MaRDI QIDQ650910

Paul G. Spirakis, Christoforos L. Raptopoulos, Sotiris E. Nikoletseas

Publication date: 7 December 2011

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

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

zbMATH Keywords

random graphsindependent setHamiltonian cycleintersection graphsprobabilistic methods

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45)

Related Items

Maximum cliques in graphs with small intersection number and random intersection graphs, Constructions of independent sets in random intersection graphs, Colouring Non-sparse Random Intersection Graphs, On Some Combinatorial Properties of Random Intersection Graphs, Hamilton cycles in the line graph of a random graph, Degree and clustering coefficient in sparse random intersection graphs, Recent advances on the Hamiltonian problem: survey III, A note on hamiltonicity of uniform random intersection graphs, Approximating fixation probabilities in the generalized Moran process, On the chromatic number of non-sparse random intersection graphs

Cites Work

• Unnamed Item
• Degree distribution of a typical vertex in a general random intersection graph
• Connectivity of the uniform random intersection graph
• Independent Sets in Random Graphs from the Weighted Second Moment Method
• Expander Properties and the Cover Time of Random Intersection Graphs
• RANDOM INTERSECTION GRAPHS WITH TUNABLE DEGREE DISTRIBUTION AND CLUSTERING
• On Random Intersection Graphs: The Subgraph Problem
• The vertex degree distribution of random intersection graphs
• Automata, Languages and Programming
• Automata, Languages and Programming
• Algorithms and Computation