2012/02/15 by Bautista-Santiago, Crevel, Cano, Javier, Fabila-Monroy, Ruy +5
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1202.3455
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.