On the hull number of some graph classes

Description

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.

Abstract

International audience

Additional details