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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.