Let ${\mathcal{P}}$ be a class of graphs. A {\em ${\mathcal{P}}$-set} in a graph $G$ is a vertex subset $X$ such that $G(X) \in {\mathcal{P}}$. We define the {\em ${\mathcal{P}}$-stability number} of a graph $G$, $\alpha_{\mathcal{P}}(G)$, as the maximum cardinality of a ${\mathcal{P}}$-set in $G$.
A {\em ${\mathcal{P}}$-dominating set} in a graph is a dominating ${\mathcal{P}}$-set. Accordingly, the {\em ${\mathcal{P}}$-domination number} of a graph $G$, $\gamma_{\mathcal{P}}(G)$, is the minimum cardinality of a ${\mathcal{P}}$-dominating set in $G$.
For each $r \ge 1$, we define a graph $G$ to be an {\em $\alpha_{\mathcal{P}}/\gamma_{\mathcal{Q}}(r)$-perfect graph} if $\alpha_{\mathcal{P}}(H)/\gamma_{\mathcal{Q}}(H) \le r$ for each induced subgraph $H$ of $G$.
We characterize all classes of
$\alpha_{\mathcal{P}}/\gamma_{\mathcal{Q}}(r)$-perfect graphs
in terms of forbidden induced subgraphs for all hereditary classes
${\mathcal{P}}$ and ${\mathcal{Q}}$ containing all edgeless graphs,
and for all real numbers $r \ge 1$.
We propose a number of related open problems and conjectures.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-47.ps.gz
DIMACS Home Page