Domination and irredundance in cubic graphs (Q1356461): Difference between revisions

This paper shows that for every positive integer \(k\) there exists a connected cubic graph \(H_k\) whose upper irredundance number \(\text{IR}(H_k)\) and upper dominating number \(\Gamma(H_k)\) satisfies \(\text{IR}(H_k)-\Gamma(H_k)\geq k\), thus disproving a conjecture of Henning and Slater, and that if \(G\) is regular, \(\text{IR}(G)\leq{1\over 2}n\). In both cases the extremal graphs are characterized and shown to satisfy \(\Gamma(G)=\text{IR}(G)\).