# zbMATH — the first resource for mathematics

Edge and vertex intersection of paths in a tree. (English) Zbl 0568.05023
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.