On two-path convexity in multipartite tournaments (Q2426441): Difference between revisions

A subset \(S\) of the vertices of a directed graph \(D\) is two-path convex if no two-path between two vertices of \(S\) contains a vertex not in \(S\). The rank of \(D\) is the size \(d(D)\) of the largest subset \(F\) of the vertices such that if \(v\) is in \(F\), then \(v\) is not in the convex hull of \(F-\{v\}\). The authors derive tight bounds for \(d(D)\) for multipartite tournaments in general and, in particular, for those in which distinct vertices do not have identical in-sets and out-sets. They also show, among other things, that the same tight bounds hold for certain other convexity parameters for these graphs, namely, the Helly number, the Radon number, and the hull number.