p-box: a new graph model

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.169--186
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01196865
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 10 septembre 2015 - 15:17:30
Dernière modification le : jeudi 11 janvier 2018 - 06:20:36
Document(s) archivé(s) le : mardi 29 décembre 2015 - 00:03:13

Fichier

dmtcs-17-1-12.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01196865, version 1

Collections

Citation

Mauricio Soto, Christopher Thraves-Caro. p-box: a new graph model. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.169--186. 〈hal-01196865〉

Partager

Métriques

Consultations de la notice

101

Téléchargements de fichiers

241