Previous |  Up |  Next


Title: On a problem concerning $k$-subdomination numbers of graphs (English)
Author: Zelinka, Bohdan
Language: English
Journal: Czechoslovak Mathematical Journal
ISSN: 0011-4642 (print)
ISSN: 1572-9141 (online)
Volume: 53
Issue: 3
Year: 2003
Pages: 627-629
Summary lang: English
Category: math
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$. (English)
Keyword: $k$-subdomination number of a graph
Keyword: three-dimensional cube graph
MSC: 05C69
idZBL: Zbl 1080.05526
idMR: MR2000058
Date available: 2009-09-24T11:05:08Z
Last updated: 2020-07-03
Stable URL:
Reference: [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
Reference: [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. Zbl 0891.05042, MR 1605689


Files Size Format View
CzechMathJ_53-2003-3_11.pdf 268.4Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo