On the connectedness and diameter of a geometric Johnson graph

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 7 Jorge Urrutia 2
1 Division de Ciencas Basicas e Ingeniera [Azcapotzalco]
2 Instituto de Matematicas [México]
3 CINVESTAV - Centro de Investigacion y de Estudios Avanzados del Instituto Politécnico Nacional
4 Departamento de Matematicas [Mexico]
5 UASLP - Facultad de Ciencas [Mexico]
6 Departament de Matemàtica Aplicada II
7 ESFM - Escuela Superior de Fisica y Matematicas [Mexico]
Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 3 (3), pp.21--30
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00966378
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 26 mars 2014 - 15:16:21
Dernière modification le : lundi 11 mars 2019 - 10:12:01
Document(s) archivé(s) le : jeudi 26 juin 2014 - 11:31:18

Fichier

2114-8348-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00966378, version 1

Collections

TDS-MACS

Citation

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. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 3 (3), pp.21--30. 〈hal-00966378〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

341

Téléchargements de fichiers

549

Contact


archive-ouverte@inria.fr