|
|
Problemy Peredachi Informatsii, 2017, Volume 53, Issue 4, Pages 3–15
(Mi ppi2249)
|
|
|
|
This article is cited in 11 scientific papers (total in 11 papers)
Coding Theory
Independence numbers of random subgraphs of some distance graph
N. M. Derevyanko, S. G. Kiselev Moscow Institute of Physics and Technology (State University), Moscow, Russia
Abstract:
The distance graph $G(n,2,1)$ is a graph where vertices are identified with twoelement subsets of $\{1,2,\dots,n\}$, and two vertices are connected by an edge whenever the corresponding subsets have exactly one common element. A random subgraph $G_p(n,2,1)$ in the Erdős–Rényi model is obtained by selecting each edge of $G(n,2,1)$ with probability p independently of other edges. We find a lower bound on the independence number of the random subgraph $G_{1/2}(n,2,1)$.
Received: 25.02.2017 Revised: 04.05.2017
Citation:
N. M. Derevyanko, S. G. Kiselev, “Independence numbers of random subgraphs of some distance graph”, Probl. Peredachi Inf., 53:4 (2017), 3–15; Problems Inform. Transmission, 53:4 (2017), 307–318
Linking options:
https://www.mathnet.ru/eng/ppi2249 https://www.mathnet.ru/eng/ppi/v53/i4/p3
|
|