MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The following theorem is a classical result (see [Alon and Spencer, The probabilistic method, 2nd ed., Theorem 1.2.2]):

Theorem: Let $G$ be a graph on $n$ vertices with minimum degree $d$. Then $G$ has a dominating set of size at most $n\tfrac{1+\ln(d+1)}{d+1}$.

In the same place it is claimed that the bound is asymptotically tight for $d$-regular graphs. This is a consequence of lower bounds on uniform hypergraph transversals (a dominating set in a graph $G$ with $n$ vertices is equivalent to a transversal of its "ball-hypergraph" on the same set of vertices, where the hyperedges are all the balls of radius 1 of the graph. This hypergraph has $n$ vertices, $n$ hyperedges, and if $G$ is $d$-regular, it is $d+1$ uniform) - see [Thomassé and Yeo, Total domination of graphs and small transversals of hypergraphs, Combinatorica, 2007].

My question is:

Question: Is this bound also asymptotically tight for $d$-regular graphs of girth 5, i.e. for any $d$, do there exist $d$-regular graphs of girth 5 with domination number $\Omega(n\tfrac{\ln(d)}{d})$?

It is known to be true when considering independent dominating sets. In fact it seems that in this case an even stronger claim holds: almost all $d$-regular graphs have girth 5, and in almost all $d$-regular graphs an independent dominating set has size at least $\Omega(n\tfrac{\ln(d)}{d})$ (when $d$ tends to infinity) (see the introduction of [A. Harutyunyan, P. Horn and J. Verstraete, Independent dominating sets in graphs of girth five, preprint]).

Now intuitively, in a $d$-regular graph of girth 5, it seems that a minimum dominating set will be "almost independent", if not independent. So I guess this result may hold for usual dominating sets as well, but I could not see any place where such a result is stated.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.