RO  EN

## Connected Dominating Sets and a New Graph Invariant

Authors: V. Bercov
Based on concept of connected dominating sets of a simple graph $G$ we introduce a new invariant $\eta(G)$ which does not exceed the number of Hadwiger. The Nordhaus-Gaddum inequalities are: $\eta(G)\eta(\overline{G})\geq n(G)$ and $\eta(G)+\eta(\overline{G})\leq 6n(G)/5$. For values of chromatic number $\chi(G)\leq 4$ we prove $\eta (G)\geq \chi (G)$. We put forward the hypothesis: the last inequality holds for all simple graphs $G$.