# On the hull number of some graph classes

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
Abstract : Given a graph $G = (V,E)$, the {\em closed interval} of a pair of vertices $u,v \in V$, denoted by $I[u,v]$, is the set of vertices that belongs to some shortest $(u,v)$-path. For a given $S\subseteq V$, let $I[S] = \bigcup_{u,v\in S} I[u,v]$. We say that $S\subseteq V$ is a {\em convex set} if $I[S] = S$. The {\em convex hull} $I_h[S]$ of a subset $S\subseteq V$ is the smallest convex set that contains $S$. We say that $S$ is a {\em hull set} if $I_h[S] = V$. The cardinality of a minimum hull set of $G$ is the {\em hull number} of $G$, denoted by $hn(G)$. We show that deciding if $hn(G)\leq k$ is an NP-complete problem, even if $G$ is bipartite. We also prove that $hn(G)$ can be computed in polynomial time for cactus and $P_4$-sparse graphs.
Type de document :
Communication dans un congrès
European Conference on Combinatorics, Graph Theory and Applications (EuroComb'11), Aug 2011, Budapest, Hungary. Elsevier, 38, pp.49-55, 2011, Electronic Notes in Discrete Mathematics. 〈10.1016/j.endm.2011.09.009〉

Littérature citée [11 références]

https://hal.inria.fr/inria-00635032
Contributeur : Ronan Pardo Soares <>
Soumis le : lundi 24 octobre 2011 - 15:34:54
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : jeudi 15 novembre 2012 - 10:22:27

### Fichier

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

### Citation

Julio Araújo, Victor Campos, Frédéric Giroire, Leonardo Sampaio, Ronan Pardo Soares. On the hull number of some graph classes. European Conference on Combinatorics, Graph Theory and Applications (EuroComb'11), Aug 2011, Budapest, Hungary. Elsevier, 38, pp.49-55, 2011, Electronic Notes in Discrete Mathematics. 〈10.1016/j.endm.2011.09.009〉. 〈inria-00635032〉

### Métriques

Consultations de la notice

## 187

Téléchargements de fichiers