Name
Abstract | ||
|---|---|---|
For a subset S of vertices of a graph G , let I G 0 ( S ) = S , I G 1 ( S ) = { v : v ¿lies¿on¿a¿shortest¿path between¿two¿vertices¿of¿ S } , and I G k ( S ) = I G 1 ( I G k - 1 ( S ) ) for k ¿ 2 . If S = I G 1 ( S ) then S is said to be a convex set. The convex hull H G ( S ) of S is the smallest convex set containing S .In this paper we study the geodetic iteration number of a graph G , defined as the smallest integer k such that H G ( S ) = I G k ( S ) for every S ¿ V ( G ) . The concept of geodetic iteration number is thus related to the interpretation of I G k ( S ) in the context of graph convexity. Computing the sequence I G 1 ( S ) , I G 2 ( S ) , ¿ 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 ) ). 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 , we give a forbidden induced subgraph characterization of distance-hereditary graphs with geodetic iteration number at most 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 g i n ( G ) when G is a distance-hereditary graph. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.disc.2015.09.025 | Discrete Mathematics |
Keywords | Field | DocType |
Convex hull,Distance-hereditary graph,Geodetic iteration number | Discrete mathematics,Graph toughness,Combinatorics,Graph property,Bound graph,Graph power,Convex set,Convex hull,Induced subgraph,Distance-hereditary graph,Mathematics | Journal |
Volume | Issue | ISSN |
339 | 2 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mitre Dourado | 1 | 90 | 18.43 |
| Rodolfo Alves de Oliveira | 2 | 4 | 1.45 |
| Fábio Protti | 3 | 357 | 46.14 |
| Dieter Rautenbach | 4 | 946 | 138.87 |