On rooted directed path graphs

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. An asteroidal quadruple is a stable set of four vertices such that any three of them is an asteroidal triple. 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 technical conditions. Cameron, Ho`ang, and L´evˆeque [DIMAP Workshop on Algorithmic Graph Theory, 67–74, Electron. Notes Discrete Math., 32, Elsevier, 2009] proved that if a pair of non adjacent vertices are linked by a special connection then in any directed path model T the subpaths of T corresponding to the vertices forming the special connection have to overlap and they force T to be completely directed in one direction between these vertices. Special connections along with the concept of asteroidal quadruple play an important role to study rooted directed path graphs, which are the intersection graphs of directed paths in a rooted directed tree. In this work we define other special connections; these special connections along with the ones defined by Cameron, Ho`ang, and L´evˆeque are nine in total, and we prove that every one forces T to be completely directed in one direction between these vertices. Also, we give a characterization of rooted directed path graphs whose rooted models cannot be rooted on a bold maximal clique. As a by-product of our result, we build new forbidden induced subgraphs for rooted directed path graphs.