Tolerant Radon partitions on the all-paths convexity in graphs

Abstract

In 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 $S\subseteq P$ with $\left|S\right|\le t$, the intersection of the convex hulls $〈P_0-S〉\cap 〈Q_0-S〉\ne \varnothing$. 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 $k=2t+2$ whenever $t\ge 1$. Finally, we prove that if the block-cut vertex tree representation of G is a path then $k=2t+3$, and if the block-cut vertex tree representation of G is a tree that is not a path then $k=2t+4$.

Keywords:

• All-paths convexity
• Radon partition
• t-tolerant Radon partition

2020 MATHEMATICS SUBJECT CLASSIFICATION:

• 05C12
• 05C38
• 52B05