inria-00576581, version 2
On the hull number of some graph classes
Julio Araujo
1, 2Victor Campos
2Frédéric Giroire
a, 1Nicolas Nisse
1Leonardo Sampaio
1Ronan Soares
1, 2
N° RR-7567 (2011)
Résumé : 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$.
- a – Polytechnique - X
- 1 : MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
- INRIA – Université de Nice Sophia Antipolis (UNS) – CNRS : UMR7271
- 2 : Parallelism, Graphs and Optimization Research Group (ParGO)
- Universidade Federal do Ceara
- Domaine : Informatique/Algorithme et structure de données
- Mots-clés : convexité des graphes – nombre enveloppe – graphes bipartis – graphes cobipartis – graphes cactus – (q – q-4)-graphes.
- Référence interne : RR-7567
- Versions disponibles : v1 (14-03-2011) v2 (14-09-2011)
- inria-00576581, version 2
- http://hal.inria.fr/inria-00576581
- oai:hal.inria.fr:inria-00576581
- Contributeur : Leonardo Sampaio
- Soumis le : Mercredi 14 Septembre 2011, 11:21:03
- Dernière modification le : Mercredi 14 Septembre 2011, 11:48:28






Documents associés
Exporter