Hull number: P5-free graphs and reduction rules

Julio Araujo 1, 2 Gregory Morel 2 Leonardo Sampaio 3 Ronan Soares 1, 2 Valentin Weber 4
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
4 G-SCOP_ROSP - ROSP
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
Abstract : In this paper, we study the (geodesic) hull number of graphs. For any two vertices $u,v\in V$ of a connected undirected graph $G=(V,E)$, the closed interval $I[u,v]$ of $u$ and $v$ is the set of vertices that belong to some shortest $(u,v)$-path. For any $S \subseteq V$, let $I[S]= \bigcup_{u,v\in S} I[u,v]$. A subset $S\subseteq V$ is (geodesically) convex if $I[S] = S$. Given a subset $S\subseteq V$, the convex hull $I_h[S]$ of $S$ is the smallest convex set that contains $S$. We say that $S$ is a hull set of $G$ if $I_h[S] = V$. The size of a minimum hull set of $G$ is the hull number of $G$, denoted by $hn(G)$. First, we show a polynomial-time algorithm to compute the hull number of any $P_5$-free triangle-free graph. Then, we present four reduction rules based on vertices with the same neighborhood. We use these reduction rules to propose a fixed parameter tractable algorithm to compute the hull number of any graph $G$, where the parameter can be the size of a vertex cover of $G$ or, more generally, its neighborhood diversity, and we also use these reductions to characterize the hull number of the lexicographic product of any two graphs.
Type de document :
Communication dans un congrès
VII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), Apr 2013, Playa del Carmen, Mexico. 2013
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-00799868
Contributeur : Julio Araujo <>
Soumis le : mardi 12 mars 2013 - 17:02:20
Dernière modification le : mercredi 7 octobre 2015 - 01:15:15
Document(s) archivé(s) le : lundi 17 juin 2013 - 12:27:33

Fichier

hull2-LAGOS-corrected-ENDM-new...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00799868, version 1

Collections

Citation

Julio Araujo, Gregory Morel, Leonardo Sampaio, Ronan Soares, Valentin Weber. Hull number: P5-free graphs and reduction rules. VII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), Apr 2013, Playa del Carmen, Mexico. 2013. 〈hal-00799868〉

Partager

Métriques

Consultations de
la notice

375

Téléchargements du document

130