2Instituto de Matematicas [México] (Instituto de Matemáticas, U.N.A.M. Área de la investigación científica, Circuito Exterior, Ciudad Universitaria Coyoacán 04510, México, D.F. México - Mexique)
4Departamento de Matematicas [Mexico] (UNAM, Facultad de Ciencias, Departamento de Matemáticas, Circuito Exterior S/N, Cd. Universitaria, Colonia Copilco el Bajo, Delegación Coyoacán, México D.F. C.P. 04510 - Mexique)
5UASLP - Facultad de Ciencas [Mexico] (Universidad Autonoma de San Luis Potosi Facultad de Ingeniería Av. Dr. Manuel Nava 8 Edifico P Zona Universitaria San Luis Potosi SLP 78290 Mexico - Mexique)
6Departament de Matemàtica Aplicada II (Universitat Politècnica de Catalunya (UPC) Edifici Omega, Campus Nord Jordi Girona, 1-3 E-08034 Barcelona Spain - Espagne)
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.
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 : mardi 19 décembre 2017 - 13:16:02
Document(s) archivé(s) le : jeudi 26 juin 2014 - 11:31:18
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〉
