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 graphArticle

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

  • 1 Division de Ciencas Basicas e Ingeniera [Azcapotzalco]
  • 2 Instituto de Matematicas [México]
  • 3 Centro de Investigacion y de Estudios Avanzados del Instituto Politécnico Nacional
  • 4 Departamento de Matematicas [Mexico]
  • 5 Facultad de Ciencas [Mexico]
  • 6 Departament de Matemàtica Aplicada II
  • 7 Escuela Superior de Fisica y Matematicas [Mexico]

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
Accepted on: June 9, 2015
Submitted on: February 15, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 471 times.
This article's PDF has been downloaded 564 times.