Menu
A graph \(G\) is claw-free if it does not contain any complete bipartite graph \(K_{1,3}\) as an induced subgraph, and closed claw-free if it is the line-graph of a triangle-free graph. The inflation \(H_1\) of a graph \(H\) is obtained from \(\mathop{H}\limits^{i}\) by replacing each vertex \(x\) of degree \(d(x)\) by a clique \(X \simeq K_{d(x)}\).
Every inflated graph \(G = H_1\) is closed claw-free.
The minimum cardinalities \(\gamma(G)\), \(\text{ir}(G)\), and \(\text{rai}(G)\) of respectively a dominating set, a maximal irredundant set, and an \(R\)-annihilated irredundant set of any graph \(G\) satisfy
\(\text{rai}(G) \leq \text{ir}(G) \leq \gamma(G).\)
The motivation of this paper is that for inflated graphs, it is known that the difference \(\gamma(G) – \text{ir}(G)\) can be arbitrarily large, but not how large the ratio \(\gamma(G)/\text{ir}(G)\) can be. We show that \(\gamma(G) \leq 3\text{rai}(G)/2\) for every claw-free graph \(G\) and study the sharpness of the bounds
\(1 \leq {\gamma(G)}/{\text{ir}(G)} \leq {\gamma(G)}/{\text{rai}(G)} \leq {3}/{2}\)
in the four classes of claw-free graphs, closed claw-free graphs, inflated graphs, and line graphs of bipartite graphs.