|
Problemy Peredachi Informatsii, 2017, Volume 53, Issue 4, Pages 3–15
(Mi ppi2249)
|
|
|
|
This article is cited in 9 scientific papers (total in 9 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
|
Statistics & downloads: |
Abstract page: | 215 | Full-text PDF : | 51 | References: | 35 | First page: | 7 |
|