# Hull number: $P 5$-free graphs and reduction rules

Hull number: $P 5$-free graphs and reduction rules - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués 2 ParGO - Parallelism, Graphs and Optimization Research Group 3 G-SCOP - Laboratoire des sciences pour la conception, l-optimisation et la production

Abstract : In this paper, we study the geodesic hull number of graphs. For any two vertices $u,v\in V$ of a connected undirected graph $G=V,E$, the closed interval $Iu,v$ of $u$ and $v$ is the set of vertices that belong to some shortest $u,v$-path. For any $S \subseteq V$, let $IS= \bigcup {u,v\in S} Iu,v$. A subset $S\subseteq V$ is geodesically convex if $IS = S$. Given a subset $S\subseteq V$, the convex hull $I hS$ of $S$ is the smallest convex set that contains $S$. We say that $S$ is a hull set of $G$ if $I hS = V$. The size of a minimum hull set of $G$ is the hull number of $G$, denoted by $hnG$. First, we show a polynomial-time algorithm to compute the hull number of any $P 5$-free triangle-free graph. Then, we present four reduction rules based on vertices with the same neighborhood. We use these reduction rules to propose a fixed parameter tractable algorithm to compute the hull number of any graph $G$, where the parameter can be the size of a vertex cover of $G$ or, more generally, its neighborhood diversity, and we also use these reductions to characterize the hull number of the lexicographic product of any two graphs.

Résumé : Dans cet article, nous étudions le \emph{nombre enveloppe} géodésique des graphes. Pour deux sommets $u$ et $v \in V$ d-un graphe connexe non orienté $G = V,E$, l-intervalle fermé $Iu,v$ de $u$ et $v$ est l-ensemble des sommets qui appartiennent á une plus courte chaîne reliant $u$ et $v$. Pour tout $S \subseteq V$, on note $IS = \bigcup {u,v \in S} Iu,v$. Un sous-ensemble $S \subseteq V$ est géodésiquement convexe si $IS = S$. Étant donné un sous-ensemble $S \subseteq V$, l-enveloppe convexe $I hS$ de $S$ est le plus petit ensemble convexe qui contient $S$. On dit que $S$ est un \emph{ensemble enveloppe} de $G$ si $I hS = V$. La taille d-un ensemble enveloppe minimum de $G$ est le nombre enveloppe de $G$, noté $hnG$. Tout d-abord, nous donnons un algorithme polynomial pour calculer le nombre enveloppe d-un graphe sans $P 5$ et sans triangle. Ensuite, nous présentons quatre régles de réductions basées sur des sommets ayant même voisinage. Nous utilisons ces régles de réduction pour proposer un algorithme FPT pour calculer le nombre enveloppe de n-importe quel graphe $G$, ou le paramétre peut être la taille d-un transversal de $G$ ou, plus généralement sa diversité de voisinage ; nous utilisons également ces régles pour caractériser le nombre enveloppe du produit lexicographique de deux graphes.

Keywords : Graph Convexity Hull Number Geodesic Convexity $P 5$-free Graphs Lexicographic Product Parameterized Complexity Neighborhood Diversity

Autor: Julio Araujo - Gregory Morel - Leonardo Sampaio - Ronan Soares - Valentin Weber -

Fuente: https://hal.archives-ouvertes.fr/

DESCARGAR PDF