DIMACS TR: 2000-45

On the ratio of the stability number and the domination number

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


Let $\alpha(G)$ and $\gamma(G)$ be the stability number and domination number of a graph $G$, respectively. Since $\alpha(G) \ge \gamma(G)$, $\alpha(G)/\gamma(G) \ge 1$. For each $r \ge 1$, we define a graph $G$ to be an {\em $\alpha/\gamma \le r$-perfect graph} if $\alpha(H)/\gamma(H) \le r$ for each induced subgraph $H$ of $G$.

We show that the class of all $\alpha/\gamma \le r$-perfect graphs is determined by a unique forbidden induced subgraph.

It gives the possibility to approximate $\alpha(G)$ and $\gamma(G)$ in the corresponding classes.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-45.ps.gz

DIMACS Home Page