Geodesic
On a problem concerning $k$-subdomination numbers of graphs
Czechoslovak Mathematical Journal, Tome 53 (2003) no. 3, pp. 627-629
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
Classification : 05C69
Keywords: $k$-subdomination number of a graph; three-dimensional cube graph 
@article{CMJ_2003_53_3_a10,
     author = {Zelinka, Bohdan},
     title = {On a problem concerning $k$-subdomination numbers of graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {627--629},
     year = {2003},
     volume = {53},
     number = {3},
     mrnumber = {2000058},
     zbl = {1080.05526},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2003_53_3_a10/}
}
TY  - JOUR
AU  - Zelinka, Bohdan
TI  - On a problem concerning $k$-subdomination numbers of graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2003
SP  - 627
EP  - 629
VL  - 53
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/CMJ_2003_53_3_a10/
LA  - en
ID  - CMJ_2003_53_3_a10
ER  - 
%0 Journal Article
%A Zelinka, Bohdan
%T On a problem concerning $k$-subdomination numbers of graphs
%J Czechoslovak Mathematical Journal
%D 2003
%P 627-629
%V 53
%N 3
%U http://geodesic.mathdoc.fr/item/CMJ_2003_53_3_a10/
%G en
%F CMJ_2003_53_3_a10
Zelinka, Bohdan. On a problem concerning $k$-subdomination numbers of graphs. Czechoslovak Mathematical Journal, Tome 53 (2003) no. 3, pp. 627-629. http://geodesic.mathdoc.fr/item/CMJ_2003_53_3_a10/

[1] E. J.  Cockayne and C. M.  Mynhardt: On a generalization of signed dominating functions of graphs. Ars Cobin. 43 (1996), 235–245. | MR

[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 | Zbl