5
$\begingroup$

Let $\gamma(G)$ and $\alpha(G)$ be the domination number and independence number for an Graph $G$. Further, let $i(G)$ be the minimum-size Independent Dominating Set. Then, it is known that $\forall G, \gamma(G) \leq i(G) \leq \alpha(G)$.

According to this paper, it is also known that $\gamma(G) = i(G)$ for Claw-free Graphs and $i(G) = \alpha(G)$ for Block Graphs.

What is the most general family of graphs for which $\gamma(G)=i(G)=\alpha(G)$? Further, what is the most general family of graphs for which $\frac{\alpha(G)}{c}\leq\gamma(G)\leq \alpha(G)$ for a constant c >1?

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "the most general family"? A characterisation like this: $G$ has $\gamma(G) = i(G)$ if and only if $G$ has some property $\Phi$? $\endgroup$ – Dominic van der Zypen Oct 25 '17 at 9:20
  • $\begingroup$ yes, that is correct. $\endgroup$ – Ainesh Bakshi Oct 26 '17 at 3:54
5
$\begingroup$

Since $\gamma(G)\leq i(G)\leq \alpha(G)$ for all graphs $G$, the problem of characterizing all graphs $G$ for which $\gamma(G)=i(G)=\alpha(G)$ is equivalent to the characterizing all graphs $G$ for which $\gamma(G)=\alpha(G)$. The theorem "$\gamma(G)=i(G)$ holds for all claw-free graphs $G$" was proved by Bollobas and Cockayne in

"B. Bollobas and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory" 3 (1979), 241-249.

However, the problem of finding the family of all graphs $G$ for which $\gamma(G)=\alpha(G)$ is still open.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.