On the hull number of some graph classes

Julio Araujo; V. Campos; Frédéric Giroire; Leonardo Sampaio; R. Soares

inria-00576581, version 1

On the hull number of some graph classes

Julio Araujo () ^1, 2, V. Campos () ², Frédéric Giroire ()^a^, 1, Leonardo Sampaio () ¹, R. Soares () ^1, 2

N° RR-7567 (2011)

Résumé : 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 a NP-complete problem, even if $G$ is bipartite and we prove that $hn(G)$ can be computed in polynomial time for cactus and $P_4$-sparse graphs.

a – Polytechnique - X
1 : MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
2 : Parallelism, Graphs and Optimization Research Group (ParGO)
Universidade Federal do Ceara

inria-00576581, version 1
http://hal.inria.fr/inria-00576581
oai:hal.inria.fr:inria-00576581
Contributeur : Leonardo Sampaio <>
Soumis le : Lundi 14 Mars 2011, 17:02:02
Dernière modification le : Mercredi 23 Mars 2011, 15:26:00

Voir la fiche détaillée

Documents associés

PDF :

Exporter

Bibtex EndNote TEI RefWorks

%F inria-00576581, version 1
%0 Report
%U http://hal.inria.fr/inria-00576581
%2 INFO:INFO_DS
%T On the hull number of some graph classes
%A Araujo, Julio
%A Campos, V.
%A Giroire, Frédéric
%A Sampaio, Leonardo
%A Soares, R.
%+ MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S , Parallelism, Graphs and Optimization Research Group - ParGO
%X 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 a NP-complete problem, even if $G$ is bipartite and we prove that $hn(G)$ can be computed in polynomial time for cactus and $P_4$-sparse graphs.
%2 Étant donné un graphe $G = (V,E)$, l'intervalle fermé d'une paire de sommets $u,v \in V$, noté $I[u,v]$, est l'ensemble des sommets qui appartiennent à tous les plus courts chemins entre $u$ et $v$. Pour un ensemble $S\subseteq V$, on note $I[S]$ l'ensemble $\bigcup_{u,v\in S} I[u,v]$. De plus, $S\subseteq V$ est dit {\it convexe} si $I[S] = S$. L'{\it enveloppe convexe} $I_h[S]$ d'un sous-ensemble $S\subseteq V$ de $G$ est défini comme le plus petit ensemble convexe qui contient $S$. $S\subseteq V$ est une {\it enveloppe} si $I_h[S] = V$. Le {\it nombre enveloppe} de $G$, noté $hn(G)$, est la cardinalité minimum d'une enveloppe de graphe $G$. Nous montrons que décider si $hn(G) \leq k$ est un problème NP-complet, même si $G$ est biparti et nous prouvons que $hn(G)$ peut être calculé en temps polynomial pour les cactus et pour les graphes $P_4$-épars.
%G Anglais
%2 Rapport de recherche
%P 12
%8 2011-03-14
%K graph convexity, hull number, bipartite graph, cactus graph, $P_4$-sparse graph.
%Z RR-7567
%Z Research supported by the INRIA Equipe Associée EWIN.

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Rapports</head>
<biblStruct type="report" xml:id="inria-00576581"><monogr>
<author><persName><forename>Julio</forename><surname>Araujo</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / Laboratoire I3S</orgName>
<orgName type="team">MASCOTTE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Nice Sophia Antipolis [UNS]</orgName>
<orgName type="institution">CNRS : UMR7271</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">ParGO</orgName>
<orgName type="team">Parallelism, Graphs and Optimization Research Group</orgName>
<country>BR</country>
<orgName type="institution">Universidade Federal do Ceara</orgName>
</affiliation>
</author>
<author><persName><forename>V.</forename><surname>Campos</surname></persName>
<affiliation>
<orgName type="laboratory">ParGO</orgName>
<orgName type="team">Parallelism, Graphs and Optimization Research Group</orgName>
<country>BR</country>
<orgName type="institution">Universidade Federal do Ceara</orgName>
</affiliation>
</author>
<author><persName><forename>Frédéric</forename><surname>Giroire</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / Laboratoire I3S</orgName>
<orgName type="team">MASCOTTE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Nice Sophia Antipolis [UNS]</orgName>
<orgName type="institution">CNRS : UMR7271</orgName>
</affiliation>
</author>
<author><persName><forename>Leonardo</forename><surname>Sampaio</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / Laboratoire I3S</orgName>
<orgName type="team">MASCOTTE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Nice Sophia Antipolis [UNS]</orgName>
<orgName type="institution">CNRS : UMR7271</orgName>
</affiliation>
</author>
<author><persName><forename>R.</forename><surname>Soares</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / Laboratoire I3S</orgName>
<orgName type="team">MASCOTTE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Nice Sophia Antipolis [UNS]</orgName>
<orgName type="institution">CNRS : UMR7271</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">ParGO</orgName>
<orgName type="team">Parallelism, Graphs and Optimization Research Group</orgName>
<country>BR</country>
<orgName type="institution">Universidade Federal do Ceara</orgName>
</affiliation>
</author>
<title type="main" level="m">On the hull number of some graph classes</title><title type="main" level="m">On the hull number of some graph classes</title><imprint><biblScope type="publicationDate">2011-03-14</biblScope><biblScope type="pp">12</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00576581</idno><idno type="HALFile">http://hal.inria.fr/inria-00576581/PDF/hn-RR.pdf</idno></biblStruct>
</listBibl>
</listBibl>