On the hull number of some graph classes

Julio Araujo 1, 2 Victor Campos 1, 2 Frédéric Giroire 2 Nicolas Nisse 2 Leonardo Sampaio 2 Ronan Soares 1, 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In this paper, we study the geodetic convexity of graphs focusing on the problem of the complexity to compute a 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 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 geodesically convex or 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 convex hull $I_h[S]$ of $S$ is the smallest convex set that contains $S$. We say that $S$ is a hull set of $G$ if $I_h[S] = V$. The size of a minimum hull set of $G$ is the 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 {\it 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 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$.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2013, 475, pp.1-12. <10.1016/j.tcs.2012.12.035>
Liste complète des métadonnées

https://hal.inria.fr/hal-00770650
Contributeur : Julio Araujo <>
Soumis le : lundi 7 janvier 2013 - 12:07:34
Dernière modification le : mercredi 7 octobre 2015 - 01:15:05
Document(s) archivé(s) le : lundi 8 avril 2013 - 11:20:39

Fichier

Hull-TCS-Corrected.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Julio Araujo, Victor Campos, Frédéric Giroire, Nicolas Nisse, Leonardo Sampaio, et al.. On the hull number of some graph classes. Theoretical Computer Science, Elsevier, 2013, 475, pp.1-12. <10.1016/j.tcs.2012.12.035>. <hal-00770650>

Partager

Métriques

Consultations de
la notice

281

Téléchargements du document

118