Hull number: -free graphs and reduction rules

详细信息    查看全文

• 作者：J. Araujo^a ; ^b ; ^c ; ^{julio@mat.ufc.br" class="auth_mail" title="E-mail the corresponding author} ; G. Morel^a ; ^{gmorel@benomad.com" class="auth_mail" title="E-mail the corresponding author} ; L. Sampaio^e ; ^{leonardo.sampaio@uece.br" class="auth_mail" title="E-mail the corresponding author} ; R. Soares^a ; ^b ; ^{ronan.soares@ufc.br" class="auth_mail" title="E-mail the corresponding author} ; V. Weber^d ; ^f ; ^{valentin.weber@amadeus.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph convexity ; Hull number ; Geodesic convexity ; P5P5-free graphs ; Lexicographic product ; Parameterized complexity ; Neighborhood diversity
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：10 September 2016
• 年：2016
• 卷：210
• 期：Complete
• 页码：171-175
• 全文大小：392 K

文摘

In this paper, we study the (geodesic) hull number of graphs. For any two vertices u,v∈V$u,v\in V$ of a connected undirected graph G=(V,E)$G=(V,E)$, the closed interval I[u,v]$I[u,v]$ of u$u$ and v$v$ is the set of vertices that belong to some shortest (u,v)$(u,v)$-path. For any S⊆V$S\subseteq V$, let I[S]=⋃_u,v∈SI[u,v]$I\left[S\right]={\bigcup }_{u,v\in S}I[u,v]$. A subset S⊆V$S\subseteq V$ is (geodesically) convex if I[S]=S$I\left[S\right]=S$. Given a subset S⊆V$S\subseteq V$, the convex hull I_h[S]$I_h\left[S\right]$ of S$S$ is the smallest convex set that contains S$S$. We say that S$S$ is a hull set of G$G$ if I_h[S]=V$I_h\left[S\right]=V$. The size of a minimum hull set of G$G$ is the hull number of G$G$, denoted by hn(G)$hn\left(G\right)$.

First, we show a polynomial-time algorithm to compute the hull number of any P₅$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$G$, where the parameter can be the size of a vertex cover of G$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.