3
$\begingroup$

Let $G=(V,E)$ be a finite, simple, undirected graph. A dominating set is a set $D\subseteq V$ such that for all $v\in V\setminus D$ there is $d\in D$ such that $\{v,d\}\in E$. The dominating number $\gamma(G)$ is defined to be the minimum cardinality of a dominating set.

The complete graphs show that the dominating number can be very small compared to the chromatic number $\chi(G)$. However, it feels like if $\chi(G)$ is "smallish" compared to $|V|$, then $\gamma(G)$ might have a chance to be larger than $\chi(G)$.

More mathematically: Is there $r\in ]0,1[$ such that whenever $\frac{\chi(G)}{|V(G)|} < r$ then $\gamma(G) \geq \chi(G)$?

$\endgroup$

1 Answer 1

3
$\begingroup$

No. Suppose that such an $r$ exists. Choose $t \in \mathbb{N}$ such that $\frac{1}{t-1} < r$. Let $G$ be the disjoint union of $t-1$ copies of $K_{t}$. Then $|V(G)|=(t-1)t$ and $\chi(G)=t$, so $\frac{\chi(G)}{|V(G)|}=\frac{1}{t-1} < r$. But $\gamma(G)=t-1 < \chi(G)$.

Note that this example can be made connected by choosing a vertex $x$ in one copy of $K_t$ and connecting $x$ to a vertex in each of the other copies of $K_t$. This will not change the chromatic number nor the domination number.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .