# 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.
Reviewer: B.Zelinka

##### MSC:
 05C05 Trees 05C38 Paths and cycles
##### Keywords:
path graph of a tree; edge intersection graph; EPT graph
Full Text:
##### References:
  Berge, C., Graphs and hypergraphs, (1973), North-Holland Amsterdam · Zbl 0483.05029  Gavril, F., A recognition algorithm for the intersection graphs of paths in trees, Discrete math., 23, 211-227, (1978) · Zbl 0398.05060  Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054  Golumbic, M.C.; Jamison, R.E., The edge intersection graphs of paths in a tree, J. combin. theory ser. B, 37, (1985) · Zbl 0537.05063  Lobb, W.A., Perfect graphs from paths in trees, (), presented at  Renz, P.L., Intersection representations of graphs by arcs, Pacific J. math., 34, 501-510, (1970) · Zbl 0191.55103  Shannon, C.E., A theorem on coloring the lines of a network, J. math. phys., 28, 148-151, (1949) · Zbl 0032.43203  Syslo, M.M., On characterizations of cycle graphs, Problémes combinatoires et théorie des graphes, 395-398, (1978), Colloq. CNRS, Orsay 1976 · Zbl 0412.05057  Syslo, M.M., On characterizations of cycle graphs and on other families of intersection graphs, () · Zbl 0418.05047  Syslo, M.M., Triangulated edge intersection graphs of paths in a tree, Discrete math., 55, 217-220, (1985) · Zbl 0569.05045  Tarjan, R.E., Decomposition by clique separators, Discrete math., 55, 221-232, (1985) · Zbl 0572.05039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.