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

05C05 Trees
05C38 Paths and cycles
Full Text: DOI
[1] Berge, C., Graphs and hypergraphs, (1973), North-Holland Amsterdam · Zbl 0483.05029
[2] Gavril, F., A recognition algorithm for the intersection graphs of paths in trees, Discrete math., 23, 211-227, (1978) · Zbl 0398.05060
[3] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[4] 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
[5] Lobb, W.A., Perfect graphs from paths in trees, (), presented at
[6] Renz, P.L., Intersection representations of graphs by arcs, Pacific J. math., 34, 501-510, (1970) · Zbl 0191.55103
[7] Shannon, C.E., A theorem on coloring the lines of a network, J. math. phys., 28, 148-151, (1949) · Zbl 0032.43203
[8] 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
[9] Syslo, M.M., On characterizations of cycle graphs and on other families of intersection graphs, () · Zbl 0418.05047
[10] Syslo, M.M., Triangulated edge intersection graphs of paths in a tree, Discrete math., 55, 217-220, (1985) · Zbl 0569.05045
[11] 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.