On maximal det-independent (res-independent) sets in graphs
Sur les ensembles maximaux indépendants de det (res-indépendants) dans les graphiques
Résumé
In this writing, we point out some errors made in [D. L. Boutin, Determining sets, resolving sets and the exchange property, Graphs and Combin., 25(2009), 789-806], where the author claims that a maximal independent set in a hereditary system is a minimal determining (resolving) set. Further more, the author claims that if the exchange property holds at the level of minimal resolving sets, then, the corresponding hereditary system is a matroid. We give counter examples to disprove both of her claims. Besides, we prove that there exist graphs having such maximal independent sets which are not necessarily determining (resolving) sets. Also, we give necessary and sufficient conditions for a class of graphs to have a maximal independent set which is not minimal determining (resolving).
Dans cet écrit, nous signalons quelques erreurs commises dans [D. L. Boutin, Ensembles déterminants, ensembles résolvants et propriété d'échange, Graphs and Combin., 25(2009), 789-806], où l'auteur affirme qu'un ensemble indépendant maximal dans un système héréditaire est un ensemble déterminant (résolvant) minimal . De plus, l'auteur prétend que si la propriété d'échange se vérifie au niveau des ensembles résolvants minimaux, alors le système héréditaire correspondant est un matroïde. Nous donnons des contre-exemples pour réfuter ses deux affirmations. De plus, nous prouvons qu'il existe des graphes ayant de tels ensembles indépendants maximaux qui ne sont pas nécessairement des ensembles déterminants (résolvants). Aussi, nous donnons des conditions nécessaires et suffisantes pour qu'une classe de graphes ait un ensemble indépendant maximal qui ne soit pas un déterminant minimal (résolution).
Origine : Fichiers produits par l'(les) auteur(s)