Path-free domination

For \(k \geq 2\), the \(P_k\)-free domination number \(\gamma(G; -P_k)\) is the minimum cardinality of a dominating set \(S\) in \(G\) such that the subgraph \(\langle S \rangle\) induced by \(S\) contains no path \(P_k\) on \(k\) vertices. The path-free domination number is at least the domination number and at most the independent domination number of the graph. We show that if \(G\) is a connected graph of order \(n \geq 2\), then \(\gamma(G; -P_k) \leq n + 2(k – 1) – 2\sqrt{n(k-1)}\), and this bound is sharp. We also give another bound on \(\gamma(G; -P_k)\) that yields the corollary: if \(G\) is a graph with \(\gamma(G) \geq 2\) that is \(K_{1,t+1}\)-free and \((K_{1,t+1}+e)\)-free (\(t \geq 3\)), then \(\gamma(G; -P_3) \leq (t-2)\gamma(G) – 2(t-3)\), and we characterize the extremal graphs for the corollary’s bound. Every graph \(G\) with maximum degree at most \(3\) is shown to have equal domination number and \(P_3\)-free domination number. We define a graph \(G\) to be \(P_k\)-domination perfect if \(\gamma(H) = \gamma(H; -P_k)\) for every induced subgraph \(H\) of \(G\). We show that a graph \(G\) is \(P_3\)-domination perfect if and only if \(\gamma(H) = \gamma(H; -P_3)\) for every induced subgraph \(H\) of \(G\) with \(\gamma(H) = 3\).