Bautista-Santiago, Crevel and Cano, Javier and Fabila-Monroy, Ruy and Flores-Peñaloza, David and González-Aguilar, Hernànet 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
On the connectedness and diameter of a geometric Johnson graph

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

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.


Source : oai:HAL:hal-00966378v1
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

Browsing statistics

This page has been seen 96 times.
This article's PDF has been downloaded 90 times.