Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418733 | Discrete Applied Mathematics | 2014 | 5 Pages |
Abstract
If SS is a set of vertices of a graph GG, then the convex hull of SS in the P3P3 convexity of GG is the smallest set TT of vertices of GG that contains SS and that has the property that no vertex in V(G)∖TV(G)∖T has at least two neighbors in TT. The Carathéodory number of the P3P3 convexity of GG is the smallest integer cc such that for every set SS of vertices of GG and every vertex uu in the convex hull of SS, there is a subset FF of SS with at most cc elements such that uu lies in the convex hull of FF. We describe a polynomial time algorithm to determine the Carathéodory number of the P3P3 convexity of a given chordal graph.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Erika M.M. Coelho, Mitre C. Dourado, Dieter Rautenbach, Jayme L. Szwarcfiter,