2006.01.24 | Gerth Stølting Brodal

Abstract:

A total dominating set $S$ in a graph $G=(V(G),E(G))$ is a set
of vertices such that every vertex in $G$ is adjacent to a vertex
in $S$. In other words $\\forall x \\in V(G)$ $\\exists s \\in S$:
$xs \\in E(G)$.

The minimum size of a total dominating set, $\\gamma_t(G)$, in a
graph, $G$, is well studied. We will talk about the following new
bounds, where $\\delta(G)$ isthe minimum degree of $G$ and $\\Delta(G)$
is the maximumdegree in $G$:

\\begin{description}
\\item[(a):] $\\gamma_t(G) \\leq \\frac{3}{7}|V(G)|$, when $\\delta(G) \\geq 4$.

\\item[(b):] $\\gamma_t(G) \\leq |V(G)| - \\frac{2|E(G)|}{\\Delta(G)+2\\sqrt{\\Delta(G)}}$,
when $\\Delta(G) \\geq 4$.
\\end{description}

In fact we can improve (a) above, if we exclude one specific graph,
$G_{14}$, on 14 vertices. In this case we can obtain the following
bound.

\\begin{description}
\\item[(c):] $\\gamma_t(G) \\leq (\\frac{3}{7}-\\frac{1}{5943})|V(G)|$, when $\\delta(G) \\geq 4$
and $G$ contains no connected components isomorphic to $G_{14}$.
\\end{description}

(b) above generalises a result by M. Henning. Using this result we can show that
the following holds, where $\\alpha'(G)$ denotes the size of a maximum matching in
a graph $G$.

\\begin{description}
\\item[(d):] If $G$ is a $k$-regular graph with $k \\geq 3$, then $\\gamma_t(G) \\leq \\alpha'(G)$.
\\end{description}

There are however examples of (non-regular) graphs, $G$, with
arbitrary high minimum degree where $\\gamma_t(G) > \\alpha'(G)$. So (d)
cannot be extended in this way. We also mention new (best possible)
lower bounds on the size of a maximum matching in connected regular
graphs. These results can be used to shorten the proofsof (d).

We will also mention other related results and open problems. Many
of the results mentioned in this talkhave been obtained by observing
that a total dominating set in a graph $G$ is also a transversal in
the hypergraph $H(G)$ on the same vertex-set as $G$ and with edge-set
$\\{ N(x) | x \\in V(G) \\}$. This allows us to use hypergraph
techniques in order to obtain the above results.

(partially joint work with S. Thomasse and M. Henning)