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.

Source : oai:HAL:hal-00966378v1

Volume: Vol. 15 no. 3

Section: Combinatorics

Published on: September 26, 2013

Submitted on: February 15, 2012

Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

This page has been seen 107 times.

This article's PDF has been downloaded 140 times.