Irredundant and perfect neighborhood sets in graphs and claw-free graphs Original Research Article

Let θ(G), θi(G), ir(G), sir(G) be the minimum cardinality of, respectively, a perfect neighborhood set, an independent perfect neighborhood set, a maximal irredundant set and a semi-maximal irredundant set of a graph G. It is clear that θ(G)⩽θi(G) and that sir(G)⩽ir(G). It has been conjectured in [5] that θ(G)⩽ir(G) for any graph G. In the first part of this paper we give a counter-example showing that the difference θ(G) − ir(G) can be arbitrarily large. In the second part we prove that for claw-free graphs, θ(G) =θi(G)⩽sir(G). We also describe the (K1,3, B1,3)-free graphs for which θ(G) = sir(G)⩾3 and the (K1,3, B1,3, C6)-free graphs for which θ(G) = sir(G) = 2, where the graphs B1,3 and C6 are shown in Fig. 1.