Recognizing clique graphs of directed and rooted path graphs. (English) Zbl 0927.05071
Summary: We describe characterizations for the classes of clique graphs of directed and rooted path graphs. The characterizations relate these classes to those of clique-Helly and strongly chordal graphs, respectively, which properly contain them. The characterizations lead to polynomial time algorithms for recognizing graphs of these classes.
MSC:
| 05C75 | Structural characterization of families of graphs |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C05 | Trees |
Keywords:
characterizations; clique graphs; path graphs; strongly chordal graphs; polynomial time algorithmsReferences:
| [1] | Bandelt, H.-J.; Prisner, E., Clique graphs and Helly graphs, J. Combin. Theory B, 51, 34-45 (1991) · Zbl 0726.05060 |
| [2] | Bornstein, C.f.; Szwarcfiter, J. L., A characterization of clique graphs of rooted path graphs, (Proceedings of the Eighth Quadriennial International Conference on Graph Theory. Proceedings of the Eighth Quadriennial International Conference on Graph Theory, Combinatorics (1996), Algorithms and Applications: Algorithms and Applications Kalamazoo, MI), in press |
| [3] | Brandstädt, A.; Dragan, F. F.; Chepoi, V. D.; Voloshin, V. I., Dually chordal graphs, SIAM J. Discrete Math., 11, 437-455 (1998) · Zbl 0909.05037 |
| [4] | Buneman, P., A characterization on rigid circuit graphs, Discrete Math., 9, 205-212 (1974) · Zbl 0288.05128 |
| [5] | Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. Symbolic Comput., 14, 251-280 (1990) · Zbl 0702.65046 |
| [6] | Dietz, P. F., Intersection graph algorithms, (Ph.D. Thesis (1994), Comp. Sci. Dept., Cornell University) |
| [7] | Escalante, F., Über iterierte Clique-Graphen, Abh. Math. Sem. Univ. Hamburg, 39, 59-68 (1973) · Zbl 0266.05116 |
| [8] | Farber, M., Domination, independent domination and duallity in strongly chordal graphs, Discrete Appl. Math., 7, 115-130 (1984) · Zbl 0531.05045 |
| [9] | Gavril, F., The intersection graphs of subtrees of a tree are exactly the chordal graphs, J. Combin. Theory B, 16, 46-56 (1974) · Zbl 0266.05101 |
| [10] | Gavril, F., A recognition algorithm for the intersection graphs of directed paths in directed trees, Discrete Math., 13, 237-249 (1975) · Zbl 0312.05108 |
| [11] | Gavril, F., A recognition algorithm for the intersection graph of paths of a tree, Discrete Math., 23, 377-388 (1978) |
| [12] | Golumbic, M.c., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054 |
| [13] | Gutierrez, M., Tree-clique graphs, Estud. Comun. Inst. Mat., 63, 7-26 (1996) |
| [14] | Gutierrez, M.; Zucchiello, R., Grafos ACI: Una generalización de los grafos de intervalo próprio (1996), preprint |
| [15] | Monma, C. L.; Wei, V. K., Intersection graphs of paths of a tree, J. Comb. Theory B, 41, 141-181 (1986) · Zbl 0595.05062 |
| [16] | Prisner, E., Graph Dynamics, (Pitman Research Notes in Mathematics, vol. 338 (1995), Longman: Longman New York) · Zbl 0848.05001 |
| [17] | Szwarcfiter, J. L., Recognizing clique-Helly graphs, Ars Combin., 45, 29-32 (1997) · Zbl 0933.05127 |
| [18] | Szwarcfiter, J. L.; Bornstein, C. F., Clique graphs of chordal and path graphs, SIAM J. Discrete Math., 7, 331-336 (1994) · Zbl 0798.05046 |
| [19] | Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Shirakawa, I., A new algorithm for generating all the maximal independent sets, SIAM J. Comput., 6, 505-517 (1977) · Zbl 0364.05027 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
