On the geodetic Radon number of grids
| Autor: | Dieter Rautenbach, Jayme Luiz Szwarcfiter, Vinícius Gusmão Pereira de Sá, Mitre Costa Dourado |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Discrete mathematics
Radon number Geodetic convexity Series (mathematics) Grid graph chemistry.chemical_element Geodetic datum Radon Cartesian product Convexity Theoretical Computer Science Combinatorics symbols.namesake chemistry Product (mathematics) Radon partition symbols Manhattan distance Discrete Mathematics and Combinatorics Focus (optics) Lattice graph Mathematics |
| Zdroj: | Discrete Mathematics. 313(1):111-121 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2012.09.007 |
| Popis: | 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 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 ≤ 9 . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect