Authors: V. Bercov
Keywords: dominating set, number of Hadwiger, chromatic number, Nordhaus-Gaddum inequalities.
Abstract
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$.
Department of Mathematics
BMCC CUNY
New York, USA
E-mail:
Fulltext
–
0.11 Mb