Carregant...
Carregant...

Vés al contingut (premeu Retorn)

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 Obrir en finestra nova
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)