8493 articles  [english version]

inria-00576581, version 1

## On the hull number of some graph classes

Julio Araujo () 12, V. Campos () 2, Frédéric Giroire () a1, Leonardo Sampaio () 1, R. Soares () 12

N° RR-7567 (2011)

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 a NP-complete problem, even if $G$ is bipartite and we prove that $hn(G)$ can be computed in polynomial time for cactus and $P_4$-sparse graphs.

• a –  Polytechnique - X
• 1 :  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
• INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
• 2 :  Parallelism, Graphs and Optimization Research Group (ParGO)
• Mots-clés : graph convexity – hull number – bipartite graph – cactus graph – $P_4$-sparse graph.