Powers of hhd-free graphsFootnote^∗

^∗First author supported by DAAD and by VW, Project No. 1/69041. second author supported by DFG.

References

• Bandelt , H. J. , Henkmann , A. and Nicolai , F. 1995 . Powers of distance-hereditary graphs . Discr. Math. , 145 : 37 – 60 .
   Google Scholar
• Brandstädt , A. , Chepoi , V. D. and Dragan , F. F. 1994 . 20th International Workshop “Graph-Theoretic Concepts in Computer Science”, WG′94 . The algorithmic use of hypertree structure and maximum neighbourhood orderings . 1994 , Herrsching, Germany. pp. 65 – 80 . LNCS 903 : Springer . (E. W. Mayr, G. Schmidt and G. Tinhofer, Eds.)
   Google Scholar
• Brandstädt A. Dragan A. Le V. B. Induced cycles and odd powers of graphs Preprint CS-09-95 University of Rostock 1995
   Google Scholar
• Chandrasekaran , R. and Doughety , A. 1981 . Location on tree networks: p-center and q-dispersion problems . Math. Oper. Res. , 6(1) : 50 – 57 .
   Google Scholar
• Chang , G. J. and Nemhauser , G. L. 1984 . The k-domination and k-stability problems on sun-free chordal graphs . SIAM J. Algebraic and Discrete Methods , 5 : 332 – 345 .
   Google Scholar
• Chepoi , V. 1989 . Classifying graphs by means of metric triangles (in Russian) . Meth. of Discrete Analysis , 49 Novosibirsk
   Google Scholar
• Chvatál , V. 1984 . Perfectly orderable graphs . Annals of Discrete Math. , 21 : 63 – 65 .
   Google Scholar
• Dirac , G. A. 1961 . On rigid circuit graphs . Abh. Math. Seminar Univ. Hamburg , 25 : 71 – 76 .
   Google Scholar
• Dragan , F. F. 1991 . Dominating and packing in triangulated graphs (in Russian) . Meth. of Discrete Analysis , 51 : 17 – 36 . Novosibirsk
   Google Scholar
• Dragan , F. F. and Brandstädt , A. . Proc. of the 11th STACS . r-Dominating cliques in graphs with hypertree structure . 1996 , Caen, France. Vol. 162 , pp. 735 – 746 . Springer . LNCS 775 Discrete Math. 93-108.
   Google Scholar
• Dragan F. F. Nicolai F. Brandstädt A. Convexity and HHD-free graphs Technical Report Gerhard-Mercator-Universität-Gesamthochschule Duisburg SM-DU- 290 Abstracts of the 5th International Coll. on “Graphs and Combinatorics” Marseille Luminy 3-8 September 1995
   Google Scholar
• Dragan F. F. Nicolai F. LexBFS-orderings of distance-hereditary graphs Technical Report Gerhard-Mercator-Universitat-Gesamthochschule Duisburg SM-DU- 303. 1995
   Google Scholar
• Duchet , P. 1984 . Classical perfect graphs . Annals of Discr. Math. , 21 67 – 96 .
   Google Scholar
• Gionfriddo , M. 1986 . A short survey on some generalized colourings of graphs . Ars. Comb. , 30 September : 275 – 284 .
   Google Scholar
• Golumbic , M. C. Algorithmic Graph Theory and Perfect Graphs , New York : Academic Press .
   Google Scholar
• Jamison , B. and Olariu , S. 1988 . On the semi-perfect elimination . Advances in Applied Math. , 9 : 364 – 376 .
   Google Scholar
• Jensen , T. R. and Toft , B. 1995 . Graph coloring problems , Wiley .
   Google Scholar
• Kloks , T. , Kratsch , D. and Müller , H. 1995 . Proceedings of European Symposium on Algorithms ESA′95 . Approximating the bandwidth for AT-free graphs . 1995 . pp. 434 – 447 . Springer . LNCS 979, (Ed. P. Spirakis)
   Google Scholar
• Laskar , R. and Shier , D. R. 1983 . On powers and centers of chordal graphs . Discr. Appl. Math. , 6 : 139 – 147 .
   Google Scholar
• Olariu , S. 1989 . Weak bipolarizable graphs . Discr. Math. , 74 : 159 – 171 .
   Google Scholar
• Olariu , S. 1990 . An -algorithm to recognize HHD-free graphs . Int. Journal ofComp. Math. , 31 : 177 – 185 .
   Web of Science ®Google Scholar
• Rose , D. 1970 . Triangulated graphs and the elimination process . J. Math. Anal. Appl. , 32 : 579 – 609 .
   Google Scholar
• Rose , D. , Tarjan , R. E. and Lueker , G. 1976 . Algorithmic aspects on vertex elimination on graphs . SIAM J. Computing , 5 : 266 – 283 .
   Google Scholar
• Tarjan , R. E. and Yannakakis , M. 1984 . Simple linear time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs . SIAM J. Computing , 13 ( 3 ) : 566 – 579 .
   Web of Science ®Google Scholar