On the hull number of some graph classes

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>
Liste complète des métadonnées

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

Fichier

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

Identifiants

Collections

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>

Partager

Métriques

Consultations de
la notice

146

Téléchargements du document

160