Mauricio Soto ; Christopher Thraves-Caro - p-box: a new graph model

dmtcs:2121 - Discrete Mathematics & Theoretical Computer Science, March 27, 2015, Vol. 17 no. 1 -
p-box: a new graph modelArticle

Authors: Mauricio Soto 1; Christopher Thraves-Caro 2

  • 1 Departamento de Ingeniería Matemática [Santiago]
  • 2 Departamento de Sistemas Telemáticos y Computación [Mostoles, Madrid]

In this document, we study the scope of the following graph model: each vertex is assigned to a box in ℝd and to a representative element that belongs to that box. Two vertices are connected by an edge if and only if its respective boxes contain the opposite representative element. We focus our study on the case where boxes (and therefore representative elements) associated to vertices are spread in ℝ. We give both, a combinatorial and an intersection characterization of the model. Based on these characterizations, we determine graph families that contain the model (e. g., boxicity 2 graphs) and others that the new model contains (e. g., rooted directed path). We also study the particular case where each representative element is the center of its respective box. In this particular case, we provide constructive representations for interval, block and outerplanar graphs. Finally, we show that the general and the particular model are not equivalent by constructing a graph family that separates the two cases.

Volume: Vol. 17 no. 1
Section: Graph Theory
Published on: March 27, 2015
Submitted on: September 19, 2013
Keywords: boxicity 2 graphs,(max-)tolerance graphs,intersection graphs,disk graphs,graph representation,Graph theory,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]

1 Document citing this article

Consultation statistics

This page has been seen 442 times.
This article's PDF has been downloaded 730 times.