Bounds relating generalized domination parameters
The paper studies a generalization of the domination number of a graph. For any integer \(n\geq 2\) the vertices \(u\), \(v\) of a graph \(G\) are said to be \(K_ n\)-adjacent, if there is a subgraph of \(G\) isomorphic to the complete graph \(K_ n\) with \(n\) vertices and containing the vertices \(u\), \(v\). A subset \(D\) of the vertex set \(V(G)\) of \(G\) is called \(K_ n\)-dominating (or total \(K_ n\)-dominating), if for every \(x\in V(G)-D\) (or every \(x \in D\), respectively) there exists a vertex \(y\in D\) which is \(K_ n\)-adjacent to \(x\). The minimum number of vertices of a \(K_ n\)-dominating (or total \(K_ n\)-dominating) set in \(G\) is called the \(K_ n\)-domination number (or total \(K_ n\)-domination number) of \(G\) and denoted by \(\gamma_{K_ n}(G)\) (or \(\gamma^ t_{K_ n}(G)\), respectively). In the paper two inequalities for the sum \(\gamma_{K_ 3}(G)+\gamma^ t_{K_ 3}(G)\) are proved and it is conjectured that analogous inequalities hold for \(\gamma_{K_ n}(G)+\gamma^ t_{K_ n}(G)\) in general.
scientific article; zbMATH DE number 429137
scientific article