An upper bound on the P-3-Radon number

作者：Dourado Mitre C; Rautenbach Dieter^*; dos Santos Vinicius Fernandes; Schaefer Philipp M; Szwarcfiter Jayme L; Toman Alexandre

来源：Discrete Mathematics, 2012, 312(16): 2433-2437.

DOI：10.1016/j.disc.2012.05.002

• Graph convexity
• Radon partition
• Radon number

The generalization of classical results about convex sets in R-n to abstract convexity spaces, defined by sets of paths in graphs, leads to many challenging structural and algorithmic problems. Here we study the Radon number for the P-3-convexity on graphs. A set R of vertices of a graph G is P-3-convex if no vertex in V (G) \ R has two neighbours in R. The P-3-convex hull of a set of vertices is the smallest P-3-convex set containing it. The P-3-Radon number r(G) of a graph G is the smallest integer r such that every set R of r vertices of G has a partition R = R-1 U R-2 such that the P-3-convex hulls of R-1 and R-2 intersect. We prove that r(G) %26lt;= 2/3(n(G) + 1) + 1 for every connected graph G and characterize all extremal graphs.

• 出版日期2012-8-28