Tolerant Radon partitions on the all-paths convexity in graphs

Abstract

AbstractIn a graph G, the all-paths transit function A(u, v), consists of the set of all vertices in the graph G which lies in some path connecting u and v. Convexity obtained by the all-paths transit function is called all-paths convexity. A partition of a set P of vertices of a graph G into two disjoint non-empty subsets is called a Radon partition if the convex hulls of the subsets intersect. A Radon partition (P0, Q0) of P into nonempty subsets is called t-tolerant Radon partition, if for any set [Formula: see text] with [Formula: see text], the intersection of the convex hulls [Formula: see text]. Here we study the t-tolerant Radon number of G with respect to all-paths convexity. It is the minimum number k such that any collection of k vertices of G has t-tolerant Radon partition. We prove that if G has only one block, then [Formula: see text] whenever [Formula: see text]. Finally, we prove that if the block-cut vertex tree representation of G is a path then [Formula: see text], and if the block-cut vertex tree representation of G is a tree that is not a path then [Formula: see text].

Keywords

• All-paths convexity
• Radon partition
• t-tolerant Radon partition
• 05C12
• 05C38
• 52B05