On the geodetic iteration number of distance-hereditary graphs

详细信息    查看全文

• 作者：Mitre C. Dourado^b ; ^{mitre@nce.ufrj.br" class="auth_mail" title="E-mail the corresponding author} ; Rodolfo A. Oliveira^b ; ^{rodolfo@nce.ufrj.br" class="auth_mail" title="E-mail the corresponding author} ; Fá ; bio Protti^a ; ^{fabio@ic.uff.br" class="auth_mail" title="E-mail the corresponding author} ; Dieter Rautenbach^c ; ^{dieter.rautenbach@uni-ulm.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Convex hull ; Distance-hereditary graph ; Geodetic iteration number
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：489-498
• 全文大小：488 K

文摘

For a subset S$S$ of vertices of a graph G$G$, let $I_G^0\left(S\right)=S$, $I_G^1\left(S\right)=\{v:v\text{lies on a shortest path}\text{between two vertices of}S\}$, and $I_G^k\left(S\right)=I_G^1\left(I_G^{k-1}\left(S\right)\right)$ for k≥2$k\ge 2$. If $S=I_G^1\left(S\right)$ then S$S$ is said to be a convex set. The convex hull H_G(S)$H_G\left(S\right)$ of S$S$ is the smallest convex set containing S$S$.

In this paper we study the geodetic iteration number of a graph G$G$, defined as the smallest integer k$k$ such that $H_G\left(S\right)=I_G^k\left(S\right)$ for every S⊆V(G)$S\subseteq V\left(G\right)$. The concept of geodetic iteration number is thus related to the interpretation of $I_G^k\left(S\right)$ in the context of graph convexity. Computing the sequence $I_G^1\left(S\right),I_G^2\left(S\right),\dots$ can be viewed as a special type of graph dynamics, i.e., the process of iteratively performing applications of a well-defined operator that eventually converges to a fixed point (the convex hull H_G(S)$H_G\left(S\right)$). Therefore, the geodetic iteration number is a natural graph invariant that tells us the minimum number of iterations to guarantee the convergence of any initial subset, providing a measure of nonconvexity of the convex space defined over the graph.

For each positive integer k$k$, we give a forbidden induced subgraph characterization of distance-hereditary graphs with geodetic iteration number at most k$k$. Distance-hereditary graphs play an important role in the study of geodesic convexity, since for such graphs the distances between vertices are preserved in connected induced subgraphs. As a consequence of our results, we describe a polynomial-time algorithm for the computation of gin(G)$gin\left(G\right)$ when G$G$ is a distance-hereditary graph.