| 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:
|
http://hdl.handle.net/10338.dmlcz/127828 |
| . |
| 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 |
| . |
