Characterizing Directed Path Graphs by Forbidden Asteroids

Abstract : An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal graph is an interval graph if and only if it does not contain an asteroidal triple. In this paper, we prove an analogous theorem for directed path graphs which are the intersection graphs of directed paths in a directed tree. For this purpose, we introduce the notion of a special connection. Two non-adjacent vertices are linked by a special connection if either they have a common neighbor or they are the endpoints of two vertex-disjoint chordless paths satisfying certain conditions. A special asteroidal triple is an asteroidal triple such that each pair is linked by a special connection. We prove that a chordal graph is a directed path graph if and only if it does not contain a special asteroidal triple.
Type de document :
Article dans une revue
Journal of Graph Theory, Wiley, 2011, 68, pp.103-112. 〈10.1002/jgt.20543〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00627742
Contributeur : Benjamin Lévêque <>
Soumis le : jeudi 29 septembre 2011 - 14:51:46
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Lien texte intégral

Identifiants

Collections

Citation

Kathie Cameron, Chinh Hoàng, Benjamin Lévêque. Characterizing Directed Path Graphs by Forbidden Asteroids. Journal of Graph Theory, Wiley, 2011, 68, pp.103-112. 〈10.1002/jgt.20543〉. 〈lirmm-00627742〉

Partager

Métriques

Consultations de la notice

83