HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

On the hull number of some graph classes

Julio Araujo 1, 2 Victor Campos 2 Frédéric Giroire 1 Nicolas Nisse 1 Leonardo Sampaio 1 Ronan Soares 1, 2
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 : In this paper, we study the geodetic convexity of graphs focusing on the problem of the complexity to compute inclusion-minimum hull set of a graph in several graph classes. For any two vertices $u,v\in V$ of a connected graph $G=(V,E)$, the {\em closed interval} $I[u,v]$ of $u$ and $v$ is the the set of vertices that belong to some shortest $(u,v)$-path. For any $S \subseteq V$, let $I[S]= \bigcup_{u,v\in S} I[u,v]$. A subset $S\subseteq V$ is {\em geodesically convex} if $I[S] = S$. In other words, a subset $S$ is convex if, for any $u,v \in S$ and for any shortest $(u,v)$-path $P$, $V(P) \subseteq S$. Given a subset $S\subseteq V$, the {\em convex hull} $I_h[S]$ of $S$ is the smallest convex set that contains $S$. We say that $S$ is a {\em hull set} of $G$ if $I_h[S] = V$. The size of a minimum hull set of $G$ is the {\em hull number} of $G$, denoted by $hn(G)$. The {\sc Hull Number} problem is to decide whether $hn(G)\leq k$, for a given graph $G$ and an integer $k$. Dourado {\it et al.} showed that this problem is NP-complete in general graphs. In this paper, we answer an open question of Dourado et al.~\cite{Douradoetal09} by showing that the {\sc Hull Number} problem is NP-hard even when restricted to the class of bipartite graphs. Then, we design polynomial time algorithms to solve the {\sc Hull Number} problem in several graph classes. First, we deal with the class of complements of bipartite graphs. Then, we generalize some results in~\cite{ACGSS11} to the class of $(q,q-4)$-graphs and to the class of cacti. Finally, we prove tight upper bounds on the hull numbers. In particular, we show that the hull number of an $n$-node graph $G$ without simplicial vertices is at most $1+\lceil \frac{3(n-1)}{5}\rceil$ in general, at most $1+\lceil \frac{n-1}{2}\rceil$ if $G$ is regular or has no triangle, and at most $1+\lceil \frac{n-1}{3}\rceil$ if $G$ has girth at least $6$.
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00576581
Contributor : Leonardo Sampaio Connect in order to contact the contributor
Submitted on : Wednesday, September 14, 2011 - 11:21:03 AM
Last modification on : Friday, February 4, 2022 - 3:18:17 AM
Long-term archiving on: : Tuesday, November 13, 2012 - 10:45:37 AM

File

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

Identifiers

  • HAL Id : inria-00576581, version 2

Collections

Citation

Julio Araujo, Victor Campos, Frédéric Giroire, Nicolas Nisse, Leonardo Sampaio, et al.. On the hull number of some graph classes. [Research Report] RR-7567, INRIA. 2011, pp.19. ⟨inria-00576581v2⟩

Share

Metrics

Record views

243

Files downloads

554