The irredundance number and maximum degree of a graph (Q793760)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The irredundance number and maximum degree of a graph |
scientific article |
Statements
The irredundance number and maximum degree of a graph (English)
0 references
1984
0 references
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.
0 references
irredundance number
0 references
maximum degree
0 references
irredundance
0 references
communication network
0 references