Random subcube intersection graphs. I: Cliques and covering
From MaRDI portal
Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Abstract: We study random subcube intersection graphs, that is, graphs obtained by selecting a random collection of subcubes of a fixed hypercube to serve as the vertices of the graph, and setting an edge between a pair of subcubes if their intersection is non-empty. Our motivation for considering such graphs is to model `random compatibility' between vertices in a large network. For both of the models considered in this paper, we determine the thresholds for covering the underlying hypercube and for the appearance of s-cliques. In addition we pose some open problems.
Recommendations
Cites work
- scientific article; zbMATH DE number 3167451 (Why is no real title available?)
- An evolution of interval graphs
- Automata, Languages and Programming
- Biclique covers and partitions
- Coloring Random Intersection Graphs and Complex Networks
- Colouring Non-sparse Random Intersection Graphs
- Component evolution in a secure wireless sensor network
- Component evolution in random intersection graphs
- Connectivity of the uniform random intersection graph
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Diameter, connectivity, and phase transition of the uniform random intersection graph
- Equivalence of a random intersection graph and G (n ,p )
- Interval graph limits
- Large cliques in sparse random intersection graphs
- Large independent sets in general random intersection graphs
- On Hamiltonicity of uniform random intersection graphs
- On Random Intersection Graphs: The Subgraph Problem
- On the connectivity of a random interval graph
- Poisson approximation of the number of cliques in random intersection graphs
- Proof of the satisfiability conjecture for large \(k\)
- Quasi-random graphs
- Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models
- Random interval graphs
- Random interval graphs
- Random subgraphs of finite graphs. III: The phase transition for the \(n\)-cube
- Sharp thresholds of graph properties, and the $k$-sat problem
- Sparse random graphs with clustering
- The Double Dixie Cup Problem
- The Evolution of Random Subgraphs of the Cube
- The asymptotic \(k\)-SAT threshold
- The phase transition in inhomogeneous random graphs
- The phase transition in site percolation on pseudo-random graphs
- The structure of strategy-proof social choice. I: General characterization and possibility results on median spaces
- The vertex degree distribution of random intersection graphs
- Threshold limits for cover times
- Topics in Intersection Graph Theory
- Turán and Ramsey properties of subcube intersection graphs
- Voting in agreeable societies
Cited in
(3)
This page was built for publication: Random subcube intersection graphs. I: Cliques and covering
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q311574)
