MATH Seminar

Title: Independent dominating sets in graphs of girth five
Seminar: Combinatorics
Speaker: Paul Horn of Emory University
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2009-09-18 at 4:00PM
Venue: W306
Download Flyer
Abstract: One of the earliest results using the probabilistic method, due independently to Lovasz, Payan and Arnautov, shows that every d-regular, n-vertex graph has a dominating set of size at most (n(1 + log(d+1)))/(d+1). In this talk, we show that if the graph has girth five, one can actually find an independent dominating set of roughly the same size, (n log(d))/d + O(n/d). This extends results of Duckworth and Wormald who studied the problem on random regular graphs, and up to the implied constant is sharp. We further construct examples showing that for irregular graphs the corresponding statement with d replaced by the minimum degree does not hold.