Portal de Periódicos da CAPES

Intersecting Diametral Balls Induced by a Geometric Graph

2022; Springer Science+Business Media; Volume: 71; Issue: 2 Linguagem: Inglês

10.1007/s00454-022-00457-x

1432-0444

Olimjoni Pirahmad, Alexandr Polyanskii, Alexey Vasilevskii,

Advanced Graph Theory Research

For a graph whose vertex set is a finite set of points in the Euclidean $$d$$ -space consider the closed (open) balls with diameters induced by its edges. The graph is called a (an open) Tverberg graph if these closed (open) balls intersect. Using the idea of halving lines, we show that (i) for any finite set of points in the plane, there exists a Hamiltonian cycle that is a Tverberg graph; (ii) for any $$ n $$ red and $$ n $$ blue points in the plane, there exists a perfect red-blue matching that is a Tverberg graph. Also, we prove that (iii) for any even set of points in the Euclidean $$d$$ -space, there exists a perfect matching that is an open Tverberg graph; (iv) for any $$ n $$ red and $$ n $$ blue points in the Euclidean $$d$$ -space, there exists a perfect red-blue matching that is a Tverberg graph.