Previous |  Up |  Next


$k$-subdomination number of a graph; three-dimensional cube graph
One of numerical invariants concerning domination in graphs is the $k$-subdomination number $\gamma ^{-11}_{kS}(G)$ of a graph $G$. A conjecture concerning it was expressed by J. H. Hattingh, namely that for any connected graph $G$ with $n$ vertices and any $k$ with $\frac{1}{2} n < k \leqq n$ the inequality $\gamma ^{-11}_{kS}(G) \leqq 2k - n$ holds. This paper presents a simple counterexample which disproves this conjecture. This counterexample is the graph of the three-dimensional cube and $k=5$.
[1] E. J.  Cockayne and C. M.  Mynhardt: On a generalization of signed dominating functions of graphs. Ars Cobin. 43 (1996), 235–245. MR 1415993
[2] J. H.  Hattingh: Majority domination and its generalizations. In: Domination in Graphs. Advanced Topics, T. W.  Haynes, S. T.  Hedetniemi, P. J.  Slater (eds.), Marcel Dekker, Inc., New York-Basel-Hong Kong, 1998. MR 1605689 | Zbl 0891.05042
Partner of
EuDML logo