TY - JOUR
T1 - On the connectedness and diameter of a geometric Johnson Graph
AU - Bautista-Santiago, C.
AU - Cano, J.
AU - Fabila-Monroy, R.
AU - Flores-Peñaloza, D.
AU - González-Aguilar, H.
AU - Lara, D.
AU - Sarmiento, E.
AU - Urrutia, J.
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
KW - Connectedness
KW - Diameter
KW - Intersection graph
KW - Islands
KW - Johnson graph
UR - http://www.scopus.com/inward/record.url?scp=84887837079&partnerID=8YFLogxK
M3 - Artículo
SN - 1462-7264
VL - 15
SP - 21
EP - 30
JO - Discrete Mathematics and Theoretical Computer Science
JF - Discrete Mathematics and Theoretical Computer Science
IS - 3
ER -