Premium
The diameter of a random subgraph of the hypercube
Author(s) -
Kulich Tomáš
Publication year - 2012
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20442
Subject(s) - struct , hypercube , dimension (graph theory) , combinatorics , mathematics , upper and lower bounds , discrete mathematics , computer science , mathematical analysis , programming language
In this paper we present an estimation for the diameter of random subgraph of a hypercube. In the article by A. V. Kostochka (Random Struct Algorithms 4 (1993) 215–229) the authors obtained lower and upper bound for the diameter. According to their work, the inequalities n + m p ≤ D ( G n ) ≤ n + m p + 8 almost surely hold as n → ∞, where n is dimension of the hypercube and m p depends only on sampling probabilities. It is not clear from their work, whether the values of the diameter are really distributed on these 9 values, or whether the inequality can be sharpened. In this paper we introduce several new ideas, using which we are able to obtain an exact result: D ( G n ) = n + m p (almost surely). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012