Packing vertices and edges in random regular graphs

Mihalis Beis, William Duckworth, Michele Zito*

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    3 Citations (Scopus)

    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 languageEnglish
    Pages (from-to)20-37
    Number of pages18
    JournalRandom Structures and Algorithms
    Volume32
    Issue number1
    DOIs
    Publication statusPublished - Jan 2008

    Fingerprint

    Dive into the research topics of 'Packing vertices and edges in random regular graphs'. Together they form a unique fingerprint.

    Cite this