RO  EN
IMI/Publicaţii/CSJM/Ediţii/CSJM v.27, n.1 (79), 2019/

Connected Dominating Sets and a New Graph Invariant

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

Adobe PDF document0.11 Mb