Trees with equal domination and tree-free domination numbers

A subset \(S\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating in \(G\), if each vertex of \(G\) either is in \(S\), or is adjacent to a vertex of \(S\). The minimum number of vertices of a dominating set in \(G\) is the domination number \(\gamma(G)\) of \(G\). Now let \(k\) be an integer, \(k\geq 2\), and let \({\mathcal T}_k\) be the class of all trees with \(k\) vertices. The tree-free domination number \(\gamma(G,-{\mathcal T}_k)\) of \(G\) is the minimum number of vertices of a dominating set \(S\) in \(G\) such that the subgraph \(\langle S\rangle\) of \(G\) induced by \(S\) contains no element of \({\mathcal T}_k\) as a subgraph. The main result is a necessary and sufficient condition for the equality \(\gamma(T)= \gamma(T,-{\mathcal T}_k)\) to hold for a tree \(T\).

Recommendations

Cited in

(7)

This page was built for publication: Trees with equal domination and tree-free domination numbers

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