Edge and vertex intersection of paths in a tree (Q1060226)

The path graph of a tree T is a graph whose vertex set is the set \({\mathcal P}\) of nontrivial simple paths in T and in which two vertices are adjacent if and only if they (as paths) have a common vertex. Similarly the edge intersection graph of paths (shortly EPT graph) of a tree T is defined; its vertex set is again \({\mathcal P}\) and two vertices are adjacent in it if and only if they have a common edge. First a theorem on maximal cliques of an EPT graph is proved. Further the authors present a characterization of graphs which are simultaneously path graphs and EPT graphs of some trees. At the end it is proved that recognizing whether a given graph is an EPT graph is an NP-complete problem.