Connected Dominating Sets and a New Graph Invariant

摘要

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$.