On the hull number of some graph classes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

On the hull number of some graph classes

Résumé

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.
Fichier principal
Vignette du fichier
hn-EuroComb11-corrected.pdf (113.74 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00635032 , version 1 (24-10-2011)

Identifiants

Citer

Julio Araújo, Victor Campos, Frédéric Giroire, Leonardo Sampaio, Ronan Pardo Soares. On the hull number of some graph classes. EuroComb'11 - European Conference on Combinatorics, Graph Theory and Applications, Rényi Institute, Aug 2011, Budapest, Hungary. pp.49-55, ⟨10.1016/j.endm.2011.09.009⟩. ⟨inria-00635032⟩
121 Consultations
276 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More