Hull number: $P_5$-free graphs and reduction rules

Description

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 $I[u,v]$ of $u$ and $v$ is 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 if $I[S] = 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)$. 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.

Abstract (French)

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é $I[u,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 $I[S] = \bigcup_{u,v \in S} I[u,v]$. Un sous-ensemble $S \subseteq V$ est (géodésiquement) convexe si $I[S] = S$. Étant donné un sous-ensemble $S \subseteq V$, l'enveloppe convexe $I_h[S]$ de $S$ est le plus petit ensemble convexe qui contient $S$. On dit que $S$ est un \emph{ensemble enveloppe} de $G$ si $I_h[S] = V$. La taille d'un ensemble enveloppe minimum de $G$ est le nombre enveloppe de $G$, noté $hn(G)$. 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.

Additional details