##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Paul Horn

#### UCSD

## Independent dominating sets in graphs of girth 5

##### Abstract:

An early result in probabilistic combinatorics, due independently to Arnautov, Payan and Lovasz is that if $G$ is a graph on $n$ vertices with minimum degree $\delta$ then $G$ contains a dominating set of size of at most $n(1+ \log(\delta+1))/(\delta+1)$. Here, under the further assumptions that $G$ is of girth at least 5 and is $d$-regular we show that, effectively, such a dominating set can be taken to be independent. That is, we show that every $n$-vertex $d$-regular graph of girth 5 contains an independent dominating set of size $(n \log d)/d + O(n/d)$ as $d \to \infty$. We further give examples showing that the girth requirement is necessary and that regularity is necessary in the sense that if $G$ has minimum degree $\delta$, the smallest independent set may be much larger than $(n \log \delta)/\delta$. This is joint work with A. Harutyunyan, and J. Verstraete.

### November 25, 2008

### 3:00 PM

### AP&M 7321

****************************