Premium
Packing vertices and edges in random regular graphs
Author(s) -
Beis Mihalis,
Duckworth William,
Zito Michele
Publication year - 2008
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.20165
Subject(s) - mathematics , combinatorics , constructive , class (philosophy) , random graph , upper and lower bounds , discrete mathematics , computer science , graph , mathematical analysis , process (computing) , artificial intelligence , operating system
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. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008