Characterization and recognition of Radon-independent sets in split graphs

作     者：Dourado, Mitre C. Rautenbach, Dieter dos Santos, Vinicius Fernandes Szwarcfiter, Jayme L. 

作者机构：Univ Ulm Inst Optimierung & Operat Res Ulm Germany Univ Fed Rio de Janeiro Inst Matemat Rio De Janeiro Brazil Univ Fed Rio de Janeiro COPPE PESC BR-21945 Rio De Janeiro Brazil 

出 版 物：《INFORMATION PROCESSING LETTERS》 (Inf. Process. Lett.)

年 卷 期：2012年第112卷第24期

页      面：948-952页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Combinatorial problems Graph algorithms Radon number Radon partition Split graph Graph convexity 

摘      要：Let R be a set of vertices of a split graph G. We characterize when R allows a partition into two disjoint set R-1 and R-2 such that the convex hulls of R-1 and R-2 with respect to the P-3-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 P-3-convexity of G and complement earlier results in this area. (c) 2012 Elsevier BM. All rights reserved.