On the connectedness and diameter of a geometric Johnson Graph Article

•  
• Overview
•  
• Research
•  
• Additional Document Info
•  
• View All
•  

Overview

abstract

• 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. © 2013 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France.

authors

• Bautista-Santiago C.
• Cano J.
• Fabila-Monroy R.
• Flores-Peñaloza D.
• González Aguilar Hernán
• Lara D.
• Sarmiento E.
• Urrutia J.

publication date

• 2013-01-01

published in

• Discrete Mathematics and Theoretical Computer Science  Journal

Research

keywords

• Connectedness; Diameter; Intersection graph; Islands; Johnson graph Connectedness; Diameter; Intersection graph; Islands; Johnson graph; Set theory; Graph theory

Additional Document Info

start page

• 21

end page

• 30

volume

• 15

issue

• 3