Distance-hereditary graph

Last updated October 02, 2022

In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph)^[1] is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.

Definition and characterization

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:^[4]

They are the graphs in which every induced path is a shortest path, or equivalently the graphs in which every non-shortest path has at least one edge connecting two non-consecutive path vertices.
They are the graphs in which every cycle of length five or more has at least two crossing diagonals.
They are the graphs in which, for every four vertices $u$ , $v$ , $w$ , and $x$ , at least two of the three sums of distances $d (u, v) + d (w, x)$ , $d (u, w) + d (v, x)$ , and $d (u, x) + d (v, w)$ are equal to each other.
They are the graphs that do not have as isometric subgraphs any cycle of length five or more, or any of three other graphs: a 5-cycle with one chord, a 5-cycle with two non-crossing chords, and a 6-cycle with a chord connecting opposite vertices.

They are the graphs that can be built up from a single vertex by a sequence of the following three operations, as shown in the illustration:
1. Add a new pendant vertex connected by a single edge to an existing vertex of the graph.
2. Replace any vertex of the graph by a pair of vertices, each of which has the same set of neighbors as the replaced vertex. The new pair of vertices are called false twins of each other.
3. Replace any vertex of the graph by a pair of vertices, each of which has as its neighbors the neighbors of the replaced vertex together with the other vertex of the pair. The new pair of vertices are called true twins of each other.
They are the graphs that can be completely decomposed into cliques and stars (complete bipartite graphs $K 1, q$ ) by a split decomposition. In this decomposition, one finds a partition of the graph into two subsets, such that the edges separating the two subsets form a complete bipartite subgraph, forms two smaller graphs by replacing each of the two sides of the partition by a single vertex, and recursively partitions these two subgraphs.^[5]
They are the graphs that have rank-width one, where the rank-width of a graph is defined as the minimum, over all hierarchical partitions of the vertices of the graph, of the maximum rank among certain submatrices of the graph's adjacency matrix determined by the partition.^[6]
They are the HHDG-free graphs, meaning that they have a forbidden graph characterization according to which no induced subgraph can be a house (the complement graph of a five-vertex path graph), hole (a cycle graph of five or more vertices), domino (six-vertex cycle plus a diagonal edge between two opposite vertices), or gem (five-vertex cycle plus two diagonals incident to the same vertex).

Relation to other graph families

Every distance-hereditary graph is a perfect graph,^[7] more specifically a perfectly orderable graph ^[8] and a Meyniel graph. Every distance-hereditary graph is also a parity graph, a graph in which every two induced paths between the same pair of vertices both have odd length or both have even length.^[9] Every even power of a distance-hereditary graph $G$ (that is, the graph $G 2 i$ formed by connecting pairs of vertices at distance at most $2 i$ in $G$ ) is a chordal graph.^[10]

Every distance-hereditary graph can be represented as the intersection graph of chords on a circle, forming a circle graph. This can be seen by building up the graph by adding pendant vertices, false twins, and true twins, at each step building up a corresponding set of chords representing the graph. Adding a pendant vertex corresponds to adding a chord near the endpoints of an existing chord so that it crosses only that chord; adding false twins corresponds to replacing a chord by two parallel chords crossing the same set of other chords; and adding true twins corresponds to replacing a chord by two chords that cross each other but are nearly parallel and cross the same set of other chords.

A distance-hereditary graph is bipartite if and only if it is triangle-free. Bipartite distance-hereditary graphs can be built up from a single vertex by adding only pendant vertices and false twins, since any true twin would form a triangle, but the pendant vertex and false twin operations preserve bipartiteness. Every bipartite distance-hereditary graph is chordal bipartite and modular.^[11]

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.^[12]

Algorithms

Distance-hereditary graphs can be recognized, and parsed into a sequence of pendant vertex and twin operations, in linear time.^[13]

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.^[14] 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.^[15] Additionally, the clique-width of any distance-hereditary graph is at most three.^[16] As a consequence, by Courcelle's theorem, efficient dynamic programming algorithms exist for many problems on these graphs.^[17]

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.^[18]

Notes

↑ Hammer & Maffray (1990).
↑ 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.
↑ McKee & McMorris (1999)
↑ Howorka (1977); Bandelt & Mulder (1986); Hammer & Maffray (1990); Brandstädt, Le & Spinrad (1999), Theorem 10.1.1, p. 147.
↑ 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).
↑ Oum (2005).
↑ Howorka (1977).
↑ Brandstädt, Le & Spinrad (1999), pp. 70–71 and 82.
↑ Brandstädt, Le & Spinrad (1999), p.45.
↑ Brandstädt, Le & Spinrad (1999), Theorem 10.6.14, p.164.
↑ Bipartite distance-hereditary graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.
↑ Cornelsen & Di Stefano (2005).
↑ 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.
↑ 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.
↑ Kloks (1996); Brandstädt, Le & Spinrad (1999), p. 170.
↑ Golumbic & Rotics (2000).
↑ Courcelle, Makowski & Rotics (2000); Espelage, Gurski & Wanke (2001).
↑ Hsieh et al. (2002); Müller & Nicolai (1993).

Related Research Articles

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph. Equivalently stated in symbolic terms an arbitrary graph $is perfect if and only if for all we have .$

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

<span class="mw-page-title-main">Meyniel graph</span> Graph where all odd cycles of length ≥ 5 has 2+ chords

In graph theory, a Meyniel graph is a graph in which every odd cycle of length five or more has at least two chords. The chords may be uncrossed or they may cross each other, as long as there are at least two of them.

In graph theory, a cograph, or complement-reducible graph, or P₄-free graph, is a graph that can be generated from the single-vertex graph K₁ by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K₁ and is closed under complementation and disjoint union.

In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order.

In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer, and independently introduced by Tyshkevich and Chernyak (1979).

In graph theory, the clique-width of a graph $G$ is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum number of labels needed to construct $G$ by means of the following 4 operations :

Creation of a new vertex $v$ with label $i$
Disjoint union of two labeled graphs $G$ and $H$
Joining by an edge every vertex labeled $i$ to every vertex labeled $j$ , where $i \neq j$
Renaming label $i$ to label $j$

In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation if it is prime with respect to the modular decomposition.

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not in general use the minimum number of colors possible.

In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.

In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from a breadth-first search, but it produces an ordering that is consistent with breadth-first search.

In the mathematical area of graph theory, an undirected graph $G$ is strongly chordal if it is a chordal graph and every cycle of even length in $G$ has an odd chord, i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle.

In graph theory, a branch of combinatorial mathematics, a block graph or clique tree is a type of undirected graph in which every biconnected component (block) is a clique.

In the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph B = (X,Y,E) in which every cycle of length at least 6 in B has a chord, i.e., an edge that connects two vertices that are a distance > 1 apart from each other in the cycle. A better name would be weakly chordal and bipartite since chordal bipartite graphs are in general not chordal as the induced cycle of length 4 shows.

In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph. A graph is prime if it has no splits. The splits of a graph can be collected into a tree-like structure called the split decomposition or join decomposition, which can be constructed in linear time. This decomposition has been used for fast recognition of circle graphs and distance-hereditary graphs, as well as for other problems in graph algorithms.

In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs that are both chordal and distance-hereditary; they include the block graphs and are a subclass of the perfect graphs.

The twin-width of an undirected graph is a natural number associated with the graph, used to study the parameterized complexity of graph algorithms. Intuitively, it measures how similar the graph is to a cograph, a type of graph that can be reduced to a single vertex by repeatedly merging together twins, vertices that have the same neighbors. The twin-width is defined from a sequence of repeated mergers where the vertices are not required to be twins, but have nearly equal sets of neighbors.

References

Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986), "Distance-hereditary graphs", Journal of Combinatorial Theory , Series B, 41 (2): 182–208, doi: 10.1016/0095-8956(86)90043-2 , MR 0859310 .
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 .
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 .
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 , ISBN 9783540241324, 9783540305590.
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 .
D'Atri, Alessandro; Moscarini, Marina (1988), "Distance-hereditary graphs, Steiner trees, and connected domination", SIAM Journal on Computing , 17 (3): 521–538, doi:10.1137/0217032, MR 0941943 .
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 .
Eppstein, David; Goodrich, Michael T.; Meng, Jeremy Yu (2006), "Delta-confluent drawings", in Healy, Patrick; Nikolov, Nikola S. (eds.), Proc. 13th Int. Symp. Graph Drawing (GD 2005), Lecture Notes in Computer Science, vol. 3843, Springer-Verlag, pp. 165–176, arXiv: cs.CG/0510024 , doi:10.1007/11618058_16, MR 2244510, S2CID 13478178 .
Espelage, W.; Gurski, F.; Wanke, E. (2001), "How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time", Proc. 27th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2001), Lecture Notes in Computer Science, vol. 2204, Springer-Verlag, pp. 117–128.
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 .
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 .
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 .
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 .
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 .
Hui, Peter; Schaefer, Marcus; Štefankovič, Daniel (2004), "Train tracks and confluent drawings", in Pach, János (ed.), Proc. 12th Int. Symp. Graph Drawing (GD 2004), Lecture Notes in Computer Science, vol. 3383, Springer-Verlag, pp. 318–328.
Kloks, T. (1996), "Treewidth of circle graphs", International Journal of Foundations of Computer Science, 7 (2): 111–120, doi:10.1142/S0129054196000099 .
Lovász, László (1972), "Normal hypergraphs and the perfect graph conjecture", Discrete Mathematics , 2 (3): 253–267, doi: 10.1016/0012-365X(72)90006-4 , MR 0302480 .
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
Müller, Haiko; Nicolai, Falk (1993), "Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs", Information Processing Letters , 46 (5): 225–230, doi:10.1016/0020-0190(93)90100-N, MR 1228792 .
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 .
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 .

External links

"Distance-hereditary graphs", Information System on Graph Classes and their Inclusions .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Hammer & Maffray (1990).

[2] 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.

[3] McKee & McMorris (1999)

[4] Howorka (1977); Bandelt & Mulder (1986); Hammer & Maffray (1990); Brandstädt, Le & Spinrad (1999), Theorem 10.1.1, p. 147.

[5] 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).

[6] Oum (2005).

[7] Howorka (1977).

[8] Brandstädt, Le & Spinrad (1999), pp. 70–71 and 82.

[9] Brandstädt, Le & Spinrad (1999), p.45.

[10] Brandstädt, Le & Spinrad (1999), Theorem 10.6.14, p.164.

[11] Bipartite distance-hereditary graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.

[12] Cornelsen & Di Stefano (2005).

[13] 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.

[14] 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.

[15] Kloks (1996); Brandstädt, Le & Spinrad (1999), p. 170.

[16] Golumbic & Rotics (2000).

[17] Courcelle, Makowski & Rotics (2000); Espelage, Gurski & Wanke (2001).

[18] Hsieh et al. (2002); Müller & Nicolai (1993).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]