On Some Combinatorial Properties of Random Intersection Graphs

DOI10.1007/978-3-319-24024-4_21zbMath1331.05199OpenAlexW2407321885MaRDI QIDQ3464482

Christoforos L. Raptopoulos, Sotiris E. Nikoletseas

Publication date: 27 January 2016

Published in: Algorithms, Probability, Networks, and Games (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-24024-4_21

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• On the complexity of the herding attack and some related attacks on hash functions
• On the isolated vertices and connectivity in random intersection graphs
• On the independence number and Hamiltonicity of uniform random intersection graphs
• Sharp thresholds for Hamiltonicity in random intersection graphs
• Maximum cliques in graphs with small intersection number and random intersection graphs
• On the independence number of random graphs
• Large independent sets in general random intersection graphs
• Expander properties and the cover time of random intersection graphs
• Equivalence of a random intersection graph and G (n ,p )
• Colouring Non-sparse Random Intersection Graphs
• The cover time of sparse random 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
• Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models
• Coloring Random Intersection Graphs and Complex Networks
• Component evolution in a secure wireless sensor network
• Zero–One Laws for Connectivity in Random Key Graphs
• Algorithms and Computation
• The chromatic number of random graphs
• Graph colouring and the probabilistic method