Abstract
In this paper we consider the problem of finding large collections of vertices and edges satisfying particular separation properties in random regular graphs of degree r, for each fixed r ≥ 3. We prove both constructive lower bounds and combinatorial upper bounds on the maximal sizes of these sets. The lower bounds are proved by analyzing a class of algorithms that return feasible solutions for the given problems. The analysis uses the differential equation method proposed by Wormald [Lectures on Approximation and Randomized Algorithms, PWN, Wassaw, 1999, pp. 239-298]. The upper bounds are proved by direct combinatorial means.
Original language | English |
---|---|
Pages (from-to) | 20-37 |
Number of pages | 18 |
Journal | Random Structures and Algorithms |
Volume | 32 |
Issue number | 1 |
DOIs | |
Publication status | Published - Jan 2008 |