Hull number: $P_5$-free graphs and reduction rules

Résumé : Dans cet article, nous étudions le \emph{nombre enveloppe} (géodésique) des graphes. Pour deux sommets $u$ et $v \in V$ d'un graphe connexe non orienté $G = (V,E)$, l'intervalle fermé $I[u,v]$ de $u$ et $v$ est l'ensemble des sommets qui appartiennent á une plus courte chaîne reliant $u$ et $v$. Pour tout $S \subseteq V$, on note $I[S] = \bigcup_{u,v \in S} I[u,v]$. Un sous-ensemble $S \subseteq V$ est (géodésiquement) convexe si $I[S] = S$. Étant donné un sous-ensemble $S \subseteq V$, l'enveloppe convexe $I_h[S]$ de $S$ est le plus petit ensemble convexe qui contient $S$. On dit que $S$ est un \emph{ensemble enveloppe} de $G$ si $I_h[S] = V$. La taille d'un ensemble enveloppe minimum de $G$ est le nombre enveloppe de $G$, noté $hn(G)$. Tout d'abord, nous donnons un algorithme polynomial pour calculer le nombre enveloppe d'un graphe sans $P_5$ et sans triangle. Ensuite, nous présentons quatre régles de réductions basées sur des sommets ayant même voisinage. Nous utilisons ces régles de réduction pour proposer un algorithme FPT pour calculer le nombre enveloppe de n'importe quel graphe $G$, ou le paramétre peut être la taille d'un transversal de $G$ ou, plus généralement sa diversité de voisinage ; nous utilisons également ces régles pour caractériser le nombre enveloppe du produit lexicographique de deux graphes.
Type de document :
Rapport
[Research Report] RR-8045, INRIA. 2012, pp.10
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00724120
Contributeur : Julio Araujo <>
Soumis le : vendredi 17 août 2012 - 17:07:27
Dernière modification le : lundi 4 décembre 2017 - 15:14:09
Document(s) archivé(s) le : dimanche 18 novembre 2012 - 02:35:23

Fichier

RR-8045.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00724120, version 1

Collections

Citation

Julio Araujo, Gregory Morel, Leonardo Sampaio, Ronan Soares, Valentin Weber. Hull number: $P_5$-free graphs and reduction rules. [Research Report] RR-8045, INRIA. 2012, pp.10. 〈hal-00724120〉

Partager

Métriques

Consultations de la notice

354

Téléchargements de fichiers

340