Letzter, S;
(2017)
Radon numbers for trees.
Discrete Mathematics
, 340
(3)
pp. 333-344.
10.1016/j.disc.2016.08.025.
Preview |
Text
radon number.pdf - Accepted Version Download (332kB) | Preview |
Abstract
We consider P_{3}-convexity on graphs, where a set U of vertices in a graph G is convex if every vertex not in U has at most one neighbour in U. Tverberg’s theorem states that every set of (k - 1) (d + 1) + 1 points in R^{d} an be partitioned into k sets with intersecting convex hulls. As a special case of Eckhoff’s conjecture, we show that a similar result holds for P_{3}-convexity in trees. A set U of vertices in a graph G is free if no vertex of G has more than one neighbour in U. We prove an inequality relating the Radon number for P_{3}-convexity in trees with the size of a maximum free set.
Type: | Article |
---|---|
Title: | Radon numbers for trees |
Open access status: | An open access version is available from UCL Discovery |
DOI: | 10.1016/j.disc.2016.08.025 |
Publisher version: | https://doi.org/10.1016/j.disc.2016.08.025 |
Language: | English |
Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions. |
Keywords: | Radon number, Graph convexity, P_{3}-convexity. |
UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
URI: | https://discovery.ucl.ac.uk/id/eprint/10107279 |
Archive Staff Only
View Item |