DIMACS TR: 2000-45
On the ratio of the stability number and the domination number
Authors: I. E. Zverovich and I. I. Zverovich
ABSTRACT
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