Skip navigation
Skip navigation

Large independent sets in random regular graphs

Duckworth, William; Zito, Michele


We present algorithmic lower bounds on the size sd of the largest independent sets of vertices in random d-regular graphs, for each fixed d ≥ 3. For instance, for d = 3 we prove that, for graphs on n vertices, sd ≥ 0.43475 n with probability approachi

CollectionsANU Research Publications
Date published: 2009
Type: Journal article
Source: Theoretical Computer Science
DOI: 10.1016/j.tcs.2009.08.025


There are no files associated with this item.

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  12 November 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator