06109896

j

06109896 Dourado, Mitre Costa Rautenbach, Dieter Pereira de S\'a, Vin{\'\i}cius Gusm\~ao Szwarcfiter, Jayme Luiz On the geodetic Radon number of grids. Discrete Math. 313, No. 1, 111-121 (2013). 2013 Elsevier Science B.V. (North-Holland), Amsterdam EN Radon partition Radon number geodetic convexity Manhattan distance grid graph Cartesian product

doi:10.1016/j.disc.2012.09.007

Summary: It is NP-hard to determine the Radon number of graphs in the geodetic convexity. However, for certain classes of graphs, this well-known convexity parameter can be determined efficiently. In this paper, we focus on geodetic convexity spaces built upon $d$-dimensional grids, which are the Cartesian products of $d$ paths. After revisiting a result of Eckhoff concerning the Radon number of $\Bbb R^{d}$ in the convexity defined by Manhattan distance, we present a series of theoretical findings that disclose some very nice combinatorial aspects of the problem for grids. We also give closed expressions for the Radon number of the product of $P_{2}$'s and the product of $P_{3}$'s, as well as computer-aided results covering the Radon number of all possible Cartesian products of d paths for $d\le 9$.