Path-free domination

Abstract

For $k\ge 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 $⟨S⟩$ 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\ge 2$, then $\gamma (G;-P_k)\le 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)\ge 2$ that is $K_{1,t+1}$-free and $(K_{1,t+1}+e)$-free ($t\ge 3$), then $\gamma (G;-P_3)\le (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$.