Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
$k$-subdomination number of a graph; three-dimensional cube graph
$k$-subdomination number of a graph; three-dimensional cube graph
Summary:
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$.
References:
[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
Search
Partner of
