On two-path convexity in multipartite tournaments (Q2426441)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On two-path convexity in multipartite tournaments |
scientific article |
Statements
On two-path convexity in multipartite tournaments (English)
0 references
22 April 2008
0 references
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.
0 references
two-path convexity
0 references
multipartite tournaments
0 references