Bounds relating generalized domination parameters

DOI10.1016/0012-365X(93)90567-DMaRDI QIDQ687110zbMATH OpenFDO

Authors Michael A. Henning, H. C. Swart

Publication date 1 November 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(93)90567-D

zbMATH Keywords

\(K_ n\)-domination number generalized domination inequalities total \(K_ n\)- domination number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Review text

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.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Bounds relating generalized domination parameters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q687110)