Random subcube intersection graphs. I: Cliques and covering

MaRDI QIDQ311574zbMATH OpenFDO

Authors Victor Falgas-Ravry, Klas Markström

Publication date 13 September 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.7375, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p43

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

large networkrandom graphsrandom intersection graphs

Mathematics Subject Classification ID

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) Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: We study random subcube intersection graphs, that is, graphs obtained by selecting a random collection of subcubes of a fixed hypercube $Q_d$ 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 $Q_d$ and for the appearance of s-cliques. In addition we pose some open problems.

Recommendations

• scientific article; zbMATH DE number 3954974
• On Random Intersection Graphs: The Subgraph Problem
• scientific article; zbMATH DE number 3889585
• Subcube Coverings of Random Spanning Subgraphs of then-Cube
• Turán and Ramsey properties of subcube intersection graphs

Cites work

• 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 )
• scientific article; zbMATH DE number 3167451 (Why is no real title available?)
• 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 asymptotic \(k\)-SAT threshold
• The Double Dixie Cup Problem
• The Evolution of Random Subgraphs of the Cube
• 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)

• Analysis of greedy algorithm for vertex covering of random graph by cubes
• On Random Intersection Graphs: The Subgraph Problem
• Turán and Ramsey properties of subcube intersection graphs

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)