DIMACS TR: 2002-47

Ratio of generalized parameters

Authors: I. E. Zverovich and I. I. Zverovich


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