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.


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.