Crevel Bautista-Santiago ; Javier Cano ; Ruy Fabila-Monroy ; David Flores-Peñaloza ; Hernàn González-Aguilar et al. - On the connectedness and diameter of a geometric Johnson graph

dmtcs:613 - Discrete Mathematics & Theoretical Computer Science, September 26, 2013, Vol. 15 no. 3 - https://doi.org/10.46298/dmtcs.613
On the connectedness and diameter of a geometric Johnson graph

Authors: Crevel Bautista-Santiago ; Javier Cano ; Ruy Fabila-Monroy ; David Flores-Peñaloza ; Hernàn González-Aguilar ; Dolores Lara ; Eliseo Sarmiento ; Jorge Urrutia

Let P be a set of n points in general position in the plane. A subset I of P is called an island if there exists a convex set C such that I = P \C. In this paper we define the generalized island Johnson graph of P as the graph whose vertex consists of all islands of P of cardinality k, two of which are adjacent if their intersection consists of exactly l elements. We show that for large enough values of n, this graph is connected, and give upper and lower bounds on its diameter.


Volume: Vol. 15 no. 3
Section: Combinatorics
Published on: September 26, 2013
Submitted on: February 15, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Consultation statistics

This page has been seen 223 times.
This article's PDF has been downloaded 409 times.