The irredundance number and maximum degree of a graph (Q793760)

Soit \(G=(V,E)\) un graphe non orienté, sans boucle ni arête multiple. Un sommet x est redondant dans X si \(N[x]\subseteq \cup_{y\in X-x}N[y]\) avec \(N[x]=\{x\}\cup \{v\in V| \quad xv\in E\}.\) Le nombre d'irredondance ir(G) est la cardinalité minimale des ensembles maximaux de sommets n'ayant pas de redondant. Les auteurs montrent que \(ir(G)\geq n/(2\Delta -1),\) n étant le nombre de sommets de G et \(\Delta\) le degré maximal.