\input zb-basic
\input zb-ioport
\iteman{io-port 06109896}
\itemau{Dourado, Mitre Costa; Rautenbach, Dieter; Pereira de S\'a, Vin{\'\i}cius Gusm\~ao; Szwarcfiter, Jayme Luiz}
\itemti{On the geodetic Radon number of grids.}
\itemso{Discrete Math. 313, No. 1, 111-121 (2013).}
\itemab
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$.
\itemrv{~}
\itemcc{}
\itemut{Radon partition; Radon number; geodetic convexity; Manhattan distance; grid graph; Cartesian product}
\itemli{doi:10.1016/j.disc.2012.09.007}
\end