Distance-hereditary graph

Distance-hereditary graph
A distance-hereditary graph.

In graph-theoretic 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.

Distance-hereditary graphs were named and first studied by Howorka (1977), although an equivalent class of graphs was already shown to be perfect in 1970 by Olaru and Sachs.[2]

It has been known for some time that the distance-hereditary graphs constitute an intersection class of graphs,[3] but no intersection model was known until one was given by Gioan & Paul (2008).

Contents

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 may 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 at least five has two or more diagonals, and in which every cycle of length exactly five has at least one pair of crossing diagonals.
  • They are the graphs in which every cycle of length five or more has at least one pair of 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.
Three operations by which any distance-hereditary graph may be constructed.
  • They are the graphs that may 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 may be completely decomposed into cliques and stars (complete bipartite graphs K1,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]

Relation to other graph families

Every distance-hereditary graph is a perfect graph[7] and more specifically a perfectly orderable graph.[8] 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 G2i formed by connecting pairs of vertices at distance at most 2i in G) is a chordal graph.[10]

Every distance-hereditary graph may be represented as the intersection graph of chords on a circle, forming a circle graph. This may 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 may 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.

The graphs that may be built from a single vertex by pendant vertices and true twins, without any false twin operations, are the chordal distance-hereditary graphs, also called ptolemaic graphs; they include as a special case the block graphs. The graphs that may 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 may equivalently be described as chordal cographs.[11]

Algorithms

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

Because distance-hereditary graphs are perfect, some optimization problems may 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.[13] 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.[14] Additionally, the clique-width of any distance-hereditary graph is at most three.[15] As a consequence, efficient dynamic programming algorithms exist for many problems on these graphs.[16]

Several other optimization problems may 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) may be found in polynomial time on a distance-hereditary graph. A Hamiltonian cycle or Hamiltonian path of any distance-hereditary graph may also be found in polynomial time.[17]

Notes

  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 (2008). 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. ^ Cornelson & Di Stefano (2005).
  12. ^ Damiand, Habib & Paul (2001); Gioan & Paul (2008). An earlier linear time bound was claimed by Hammer & Maffray (1990) but it was discovered to be erroneous by Damiand.
  13. ^ 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 & Maffrey (1990). Because distance-hereditary graphs are perfectly orderable, they may be optimally colored in linear time by using LexBFS to find a perfect ordering and then applying a greedy coloring algorithm.
  14. ^ Kloks (1996); Brandstädt, Le & Spinrad (1999), p. 170.
  15. ^ Golumbic & Rotics (2000).
  16. ^ Courcelle, Makowski & Rotics (2000); Espelage, Gurski & Wanke (2001).
  17. ^ Hsieh, Ho & Hsu (2005); Müller & Nicolai (1993).

References

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Circle graph — For the chart, see Pie chart. A circle with five chords and the corresponding circle graph. In graph theory, a circle graph is the intersection graph of a set of chords of a circle. That is, it is an undirected graph whose vertices can be… …   Wikipedia

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • Perfect graph — The Paley graph of order 9, colored with three colors and showing a clique of three vertices. In this graph and each of its induced subgraphs the chromatic number equals the clique number, so it is a perfect graph. In graph theory, a perfect… …   Wikipedia

  • Chordal graph — A cycle (black) with two chords (green). As for this part, the graph is chordal. However, removing one green edge would result in a non chordal graph. Indeed, the other green edge with three black edges would form a cycle of length four with no… …   Wikipedia

  • Cograph — The Turán graph T(13,4), an example of a cograph In graph theory, a cograph, or complement reducible graph, or P4 free graph, is a graph that can be generated from the single vertex graph K1 by complementation and disjoint union. That is, the… …   Wikipedia

  • List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia

  • Clique-width — In graph theory, the clique width of a graph G is 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 ( noted i(v) ) Disjoint union of two labeled graphs G and H …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

  • Modular decomposition — In graph theory, the modular decomposition is a decomposition of an undirected graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can… …   Wikipedia

  • Induced path — An induced path of length four in a cube. Finding the longest induced path in a hypercube is known as the snake in the box problem. In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”