Skip to Main content Skip to Navigation
Journal articles

On the connectedness and diameter of a geometric Johnson graph

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Wednesday, March 26, 2014 - 3:16:21 PM
Last modification on : Monday, November 16, 2020 - 3:56:03 PM
Long-term archiving on: : Thursday, June 26, 2014 - 11:31:18 AM


Files produced by the author(s)




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. ⟨10.46298/dmtcs.613⟩. ⟨hal-00966378⟩



Record views


Files downloads