Menu
It has been conjectured that the smallest cardinality \(\theta(G)\) of a perfect neighbourhood set of a graph is bounded above by ir\((G)\), the smallest order of a maximal irredundant set.
We prove results concerning the construction of perfect neighbourhood sets from irredundant sets which could help to resolve the conjecture and which establish that \(\theta(G) \leq \text{ir}(G)\) in certain cases.
In particular, the inequality is proved for claw-free graphs and for any graph which has an ir-set \(S\) whose induced subgraph has at most six non-isolated vertices.