Independence, Domination, Irredundance, and Forbidden Pairs

Abstract

For different properties $\mathcal{P}$ of a connected graph $G$, we characterize the connected graphs $F$ (resp. the pairs $(X,Y)$ of connected graphs) such that $G$ has Property $\mathcal{P}$ if $G$ does not admit $F$ (resp. neither $X$ nor $Y$) as an induced subgraph.

We consider here the lower independence, domination, and irredundance parameters, which are related by the well-known inequalities $ir\le \gamma \le i\le \alpha \le \mathrm{\Gamma }\le IR$, and the properties $\mathcal{P}$ correspond to the equality between some
of these parameters.