1. On a problem concerning $k$-subdomination numbers of graphs
- Creator:
- Zelinka, Bohdan
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- $k$-subdomination number of a graph and three-dimensional cube graph
- Language:
- English
- Description:
- 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$.
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public