The original definition of a distance-hereditary graph is a graph G such that, if any two vertices u and v belong to a connected induced subgraph H of G, then some shortest path connecting u and v in G must be a subgraph of H, so that the distance between u and v in H is the same as the distance in G.
Distance-hereditary graphs can also be characterized in several other equivalent ways:
The graphs that can be built from a single vertex by pendant vertices and true twins, without any false twin operations, are special cases of the Ptolemaic graphs and include the block graphs. The graphs that can be built from a single vertex by false twin and true twin operations, without any pendant vertices, are the cographs, which are therefore distance-hereditary; the cographs are exactly the disjoint unions of diameter-2 distance-hereditary graphs. The neighborhood of any vertex in a distance-hereditary graph is a cograph. The transitive closure of the directed graph formed by choosing any set of orientations for the edges of any tree is distance-hereditary; the special case in which the tree is oriented consistently away from some vertex forms a subclass of distance-hereditary graphs known as the trivially perfect graphs, which are also called chordal cographs.
Distance-hereditary graphs can be recognized, and parsed into a sequence of pendant vertex and twin operations, in linear time.
Because distance-hereditary graphs are perfect, some optimization problems can be solved in polynomial time for them despite being NP-hard for more general classes of graphs. Thus, it is possible in polynomial time to find the maximum clique or maximum independent set in a distance-hereditary graph, or to find an optimal graph coloring of any distance-hereditary graph.
Because distance-hereditary graphs are circle graphs, they inherit polynomial time algorithms for circle graphs; for instance, it is possible determine in polynomial time the treewidth of any circle graph and therefore of any distance-hereditary graph.
Additionally, the clique-width of any distance-hereditary graph is at most three. As a consequence, by Courcelle's theorem, efficient dynamic programming algorithms exist for many problems on these graphs.
Several other optimization problems can also be solved more efficiently using algorithms specifically designed for distance-hereditary graphs.
As D'Atri & Moscarini (1988) show, a minimum connected dominating set (or equivalently a spanning tree with the maximum possible number of leaves) can be found in polynomial time on a distance-hereditary graph.
A Hamiltonian cycle or Hamiltonian path of any distance-hereditary graph can also be found in polynomial time.
Hammer & Maffray (1990). - Hammer, Peter Ladislaw; Maffray, Frédéric (1990), "Completely separable graphs", Discrete Applied Mathematics, 27 (1–2): 85–99, doi:10.1016/0166-218X(90)90131-U, MR 1055593 https://doi.org/10.1016%2F0166-218X%2890%2990131-U
Olaru and Sachs showed the α-perfection of the graphs in which every cycle of length five or more has a pair of crossing diagonals (Sachs 1970, Theorem 5). By Lovász (1972), α-perfection is an equivalent form of definition of perfect graphs. - Sachs, Horst (1970), "On the Berge conjecture concerning perfect graphs", Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), Gordon and Breach, pp. 377–384, MR 0272668 https://mathscinet.ams.org/mathscinet-getitem?mr=0272668
McKee & McMorris (1999) - McKee, Terry A.; McMorris, F. R. (1999), Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, vol. 2, Philadelphia: Society for Industrial and Applied Mathematics, doi:10.1137/1.9780898719802, ISBN 0-89871-430-3, MR 1672910 https://doi.org/10.1137%2F1.9780898719802
Howorka (1977); Bandelt & Mulder (1986); Hammer & Maffray (1990); Brandstädt, Le & Spinrad (1999), Theorem 10.1.1, p. 147. - Howorka, Edward (1977), "A characterization of distance-hereditary graphs", The Quarterly Journal of Mathematics, Second Series, 28 (112): 417–420, doi:10.1093/qmath/28.4.417, MR 0485544 https://doi.org/10.1093%2Fqmath%2F28.4.417
Gioan & Paul (2012). A closely related decomposition was used for graph drawing by Eppstein, Goodrich & Meng (2006) and (for bipartite distance-hereditary graphs) by Hui, Schaefer & Štefankovič (2004). - Gioan, Emeric; Paul, Christophe (2012), "Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs", Discrete Applied Mathematics, 160 (6): 708–733, arXiv:0810.1823, doi:10.1016/j.dam.2011.05.007, S2CID 6528410 https://arxiv.org/abs/0810.1823
Oum (2005). - Oum, Sang-il (2005), "Rank-width and vertex-minors", Journal of Combinatorial Theory, Series B, 95 (1): 79–100, doi:10.1016/j.jctb.2005.03.003, MR 2156341 https://doi.org/10.1016%2Fj.jctb.2005.03.003
Howorka (1977). - Howorka, Edward (1977), "A characterization of distance-hereditary graphs", The Quarterly Journal of Mathematics, Second Series, 28 (112): 417–420, doi:10.1093/qmath/28.4.417, MR 0485544 https://doi.org/10.1093%2Fqmath%2F28.4.417
Brandstädt, Le & Spinrad (1999), pp. 70–71 and 82. - Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X https://archive.org/details/graphclassessurv0000bran
Brandstädt, Le & Spinrad (1999), p.45. - Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X https://archive.org/details/graphclassessurv0000bran
Brandstädt, Le & Spinrad (1999), Theorem 10.6.14, p.164. - Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X https://archive.org/details/graphclassessurv0000bran
Bipartite distance-hereditary graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30. http://www.graphclasses.org/classes/gc_77.html
Cornelsen & Di Stefano (2005). - Cornelsen, Sabine; Di Stefano, Gabriele (2005), "Treelike comparability graphs: characterization, recognition, and applications", Proc. 30th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2004), Lecture Notes in Computer Science, vol. 3353, Springer-Verlag, pp. 46–57, doi:10.1007/978-3-540-30559-0_4, MR 2158633, S2CID 14166894 https://doi.org/10.1007%2F978-3-540-30559-0_4
Damiand, Habib & Paul (2001); Gioan & Paul (2012). An earlier linear time bound was claimed by Hammer & Maffray (1990) but it was discovered to be erroneous by Damiand. - Damiand, Guillaume; Habib, Michel; Paul, Christophe (2001), "A simple paradigm for graph recognition: application to cographs and distance hereditary graphs" (PDF), Theoretical Computer Science, 263 (1–2): 99–111, doi:10.1016/S0304-3975(00)00234-6, MR 1846920 https://hal-lirmm.ccsd.cnrs.fr/lirmm-00090372/file/D21.PDF
Cogis & Thierry (2005) present a simple direct algorithm for maximum weighted independent sets in distance-hereditary graphs, based on parsing the graph into pendant vertices and twins, correcting a previous attempt at such an algorithm by Hammer & Maffray (1990). Because distance-hereditary graphs are perfectly orderable, they can be optimally colored in linear time by using LexBFS to find a perfect ordering and then applying a greedy coloring algorithm. - Cogis, O.; Thierry, E. (2005), "Computing maximum stable sets for distance-hereditary graphs", Discrete Optimization, 2 (2): 185–188, doi:10.1016/j.disopt.2005.03.004, MR 2155518 https://doi.org/10.1016%2Fj.disopt.2005.03.004
Kloks (1996); Brandstädt, Le & Spinrad (1999), p. 170. - Kloks, T. (1996), "Treewidth of circle graphs", International Journal of Foundations of Computer Science, 7 (2): 111–120, doi:10.1142/S0129054196000099 https://doi.org/10.1142%2FS0129054196000099
Golumbic & Rotics (2000). - Golumbic, Martin Charles; Rotics, Udi (2000), "On the clique-width of some perfect graph classes", International Journal of Foundations of Computer Science, 11 (3): 423–443, doi:10.1142/S0129054100000260, MR 1792124 https://doi.org/10.1142%2FS0129054100000260
Courcelle, Makowski & Rotics (2000); Espelage, Gurski & Wanke (2001). - Courcelle, B.; Makowski, J. A.; Rotics, U. (2000), "Linear time solvable optimization problems on graphs on bounded clique width", Theory of Computing Systems, 33 (2): 125–150, doi:10.1007/s002249910009, S2CID 15402031 https://doi.org/10.1007%2Fs002249910009
Hsieh et al. (2002); Müller & Nicolai (1993). - Hsieh, Sun-yuan; Ho, Chin-wen; Hsu, Tsan-sheng; Ko, Ming-tat (2002), "Efficient algorithms for the Hamiltonian problem on distance-hereditary graphs", Computing and Combinatorics: 8th Annual International Conference, COCOON 2002 Singapore, August 15–17, 2002, Proceedings, Lecture Notes in Computer Science, vol. 2387, Springer-Verlag, pp. 51–75, doi:10.1007/3-540-45655-4_10, ISBN 978-3-540-43996-7, MR 2064504 https://doi.org/10.1007%2F3-540-45655-4_10