On the hull number of some graph classes

Julio Araújo 1 Victor Campos 2 Frédéric Giroire 1 Leonardo Sampaio 1 Ronan Pardo Soares 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/inria-00635032
Contributor : Ronan Pardo Soares <>
Submitted on : Monday, October 24, 2011 - 3:34:54 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Thursday, November 15, 2012 - 10:22:27 AM

File

hn-EuroComb11-corrected.pdf
Files produced by the author(s)

Identifiers

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), Rényi Institute, Aug 2011, Budapest, Hungary. pp.49-55, ⟨10.1016/j.endm.2011.09.009⟩. ⟨inria-00635032⟩

Share

Metrics

Record views

226

Files downloads

336