On the hull number of some graph classes

Julio Araujo 1, 2 Victor Campos 2 Frédéric Giroire 1 Nicolas Nisse 1 Leonardo Sampaio 1 Ronan Soares 1, 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Dans cet article nous étudions une notion de convexité dans les graphes. Nous nous concentrons sur la question de la compléxité du calcul de l'enveloppe minimum d'un graphe dans le cas de diverses classes de graphes. Étant donné un graphe $G = (V,E)$, l'intervalle $I[u,v]$ entre deux sommets $u,v \in V$ est l'ensemble des sommets qui appartiennent à un plus court chemin entre $u$ et $v$. Pour un ensemble $S\subseteq V$, on note $I[S]$ l'ensemble $\bigcup_{u,v\in S} I[u,v]$. Un ensemble $S\subseteq V$ de sommets est dit {\it convexe} si $I[S] = S$. L'{\it enveloppe convexe} $I_h[S]$ d'un sous-ensemble $S\subseteq V$ de $G$ est défini comme le plus petit ensemble convexe qui contient $S$. $S\subseteq V$ est une {\it enveloppe} de $G$ si $I_h[S] = V$. Le {\it nombre enveloppe} de $G$, noté $hn(G)$, est la cardinalité minimum d'une enveloppe de graphe $G$. Nous montrons que décider si $hn(G) \leq k$ est un problème NP-complet dans la classe des graphes bipartis et nous prouvons que $hn(G)$ peut être calculé en temps polynomial pour les cobipartis, $(q,q-4)$-graphes et cactus. Nous montrons aussi des bornes supérieures du nombre enveloppe des graphes en général, des graphes sans triangles et des graphes réguliers.
Type de document :
Rapport
[Research Report] RR-7567, INRIA. 2011, pp.19
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00576581
Contributeur : Leonardo Sampaio <>
Soumis le : mercredi 14 septembre 2011 - 11:21:03
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : mardi 13 novembre 2012 - 10:45:37

Fichier

hn-RR_v2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00576581, version 2

Collections

Citation

Julio Araujo, Victor Campos, Frédéric Giroire, Nicolas Nisse, Leonardo Sampaio, et al.. On the hull number of some graph classes. [Research Report] RR-7567, INRIA. 2011, pp.19. 〈inria-00576581v2〉

Partager

Métriques

Consultations de la notice

482

Téléchargements de fichiers

427