Carregant...

Vés al contingut (premeu Retorn)

# FUTUR. Portal de la Producció Científica dels Investigadors de la UPC

## On the connectedness and diameter of a geometric Johnson Graph

Autor
Bautista, C.; Cano, J.; Fabila, R.; Flores, D.; Gonzalez, H.; Lara, M.; Sarmiento, E.; URRUTIA, J.
Tipus d'activitat
Article en revista
Revista
Discrete mathematics and theoretical computer science
Data de publicació
2013-08
Volum
15
Número
3
Pàgina inicial
21
Pàgina final
30
URL
http://www.scopus.com/record/display.url?eid=2-s2.0-84887837079&origin=resultslist&sort=plf-f&src=s&st1=%22On+the+Connectedness+and+Diameter+of+a+Geometric+Johnson+Graph%22&sid=D8BE2F746BD58250D8D745B25738D106.ZmAySxCHIBxxTXbnsoe5w%3a990&sot=q&sdt=b&sl=84&s=TITLE-ABS-KEY-AUTH%28%22On+the+Connectedness+and+Diameter+of+a+Geometric+Johnson+Graph%22%29&relpos=0&relpos=0&citeCnt=0&searchTerm=TITLE-ABS-KEY-AUTH%28\%26quot%3BOn+the+Connectedness+and+Diameter+of+a+Geometric+Johnson+Graph\%26quot%3B%29
Resum
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.
Paraules clau
Connectedness, Diameter, Intersection graph, Islands, Johnson graph

## Participants

• Bautista Santiago, Crevel  (autor)
• Cano, Javier  (autor)
• Fabila Monroy, Ruy  (autor)
• Flores Peñazola, David  (autor)
• Gonzalez Aguilar, Hernan  (autor)
• Lara Cuevas, Maria Dolores  (autor)
• Sarmiento, E.  (autor)
• Urrutia Galicia, Jorge  (autor)