The irredundance number and maximum degree of a graph. (English) Zbl 0539.05056
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.
Reviewer: G.Chaty
References:
| [1] | Allan, R. B.; Laskar, R., On domination and some related topics in graph theory, (Proc. 9th S.E. Conference on Graph Theory, Combinatorics and Computing. Proc. 9th S.E. Conference on Graph Theory, Combinatorics and Computing, Boca Raton, February, 1978 (1978), Utilitas Math: Utilitas Math Winnipeg), 43-56 · Zbl 0404.05050 |
| [2] | Cockayne, E. J.; Hedetniemi, S. T., Independence graphs, (Proc. 5th S.E. Conference on Combinatorics, Graph Theory and Computing Utilitas Mathematica. Proc. 5th S.E. Conference on Combinatorics, Graph Theory and Computing Utilitas Mathematica, Winnipeg (1974)), 471-491 · Zbl 0305.05114 |
| [3] | Cockayne, E. J.; Hedetniemi, S. T.; Miller, D. J., Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull, 21, 4, 461-468 (1978) · Zbl 0393.05044 |
| [4] | Cockayne, E. J.; Thomason, A.; Payan, C.; Favarin, O., Contributions to the theory of domination, independence and irredundance in graphs, Discrete Math, 33, 3, 249-258 (1981) · Zbl 0471.05051 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
