On the complexity of the independent set problem in triangle graphs

Abstract : We consider the complexity of the maximum independent set problem within triangle graphs, i.e., graphs G satisfying the following triangle condition: for every maximal independent set I in G and every edge uv in G¡I, there is a vertex w 2 I such that fu; v;wg is a triangle in G. We also introduce a new graph parameter (upper independent neighborhood number) and the corresponding upper independent neighborhood set problem. We show that for triangle graphs the new parameter equals to the independence number. Finally, we prove that the problems under consideration are NP-complete for triangle graphs and provide some polynomially solvable cases for these problems within triangle graphs.
Type de document :
Rapport
2009
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00679806
Contributeur : Florent Breuil <>
Soumis le : vendredi 16 mars 2012 - 13:30:36
Dernière modification le : mardi 23 octobre 2018 - 14:36:08

Identifiants

  • HAL Id : emse-00679806, version 1

Citation

Jacek Blazewicz, Alexandre Dolgui, Valery Gordon, Yury Orlovich. On the complexity of the independent set problem in triangle graphs. 2009. 〈emse-00679806〉

Partager

Métriques

Consultations de la notice

115