| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427663 | Information Processing Letters | 2012 | 5 Pages |
Abstract
Let R be a set of vertices of a split graph G. We characterize when R allows a partition into two disjoint set R1R1 and R2R2 such that the convex hulls of R1R1 and R2R2 with respect to the P3P3-convexity of G intersect. Furthermore, we describe a linear time algorithm that decides the existence of such a partition. Our results are related to the so-called Radon number of the P3P3-convexity of G and complement earlier results in this area.
► We characterize P3P3-Radon-dependent sets in split graphs. ► We describe a linear time recognition algorithm. ► Our results are related to the P3P3-Radon number.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mitre C. Dourado, Dieter Rautenbach, Vinícius Fernandes dos Santos, Jayme L. Szwarcfiter,