3
$\begingroup$

A claw-free graph is a graph that does not have a claw as an induced subgraph or contains no induced subgraph isomorphic to $K_{1,3}$. Let $\alpha(G)$ denote the maximum size of an independent set in G. Let $i(G)$ denote the minimum size of an independent dominating set. I wonder if $\alpha(G) \leq 2i(G)$?

Intuitively, each vertex of $G$ can be dominated by up to two adjacent vertices. I'm not sure that's a rigorous analysis.

$\endgroup$

1 Answer 1

0
$\begingroup$

This is essentially the same proof than for (maximal/maximum) matchings in general graphs, because independent sets in claw free graphs have nearly the same structure as matchings.

Let $I^*$ be a maximum independent set and $I$ be a maximal independent set (so also dominating). You just need to realize that any vertex of $I$ is adjacent (including the vertex itself in the neighborhood) to at most two vertices in $I^*$, and that each vertex of $I^*$ is adjacent to at least one vertex of $I$. So by a double counting argument, when counting once the vertices of $I^*$, we can choose one adjacent vertex in $I$, and we will have counted at most twice the vertices of $I$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .