Triangulated graph

In graph theory , a graph is called triangulated or chordal if and only if it satisfies one of the following equivalent conditions: ${\displaystyle G}$

• Every induced circle is a triangle. A circle is induced exactly when there are no further edges in the original graph between its nodes .
• Every minimal ab separator to two corners a and b is a clique.
• Every induced subgraph contains a simplicial vertex (Rose, 1970), i.e. a vertex whose neighbors form a clique .
• G is the intersection graph of a set of subtrees of a tree (Gavril, 1974).

properties

In triangulated graphs, the calculation of the parameters clique number , chromatic number , independence number and clique coverage number - for any graphs NP-difficult problems - can be carried out in linear time. The characterization via simplicial corners enables a chordality test in linear time. A node order of the graph is called the perfect elimination order , so that for every graph with the node set restricted (by eliminating the nodes to ) the following applies: is simplicial in . Each (in relation to the selected order) “smallest” node in forms a clique with its neighbors . ${\displaystyle (v_{1},v_{2},\ldots ,v_{n}),V=\{v_{1},v_{2},\ldots ,v_{n}\}}$ ${\displaystyle G=(V,E)}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{i-1}}$ ${\displaystyle G_{i}=(\{v_{i},\ldots ,v_{n}\},E_{i})}$ ${\displaystyle v_{i}}$ ${\displaystyle G_{i}}$ ${\displaystyle G_{i}}$

Triangulated graphs are not to be confused with the (maximally planar) triangle graphs . Triangle graphs are not all triangulated, as can be seen from a graph that consists of a circle of length , inside and outside of which there is another node that is adjacent to all nodes of the circle. Conversely, triangulated graphs do not necessarily have to be triangle graphs, as a non-planar complete graph shows. ${\displaystyle l\geq 4}$

However, triangular graphs are still referred to as triangulated graphs in the specialist literature.

literature

• Jorge L. Ramírez Alfonsín, Bruce A. Reed: Perfect Graphs . Wiley 2001, ISBN 978-0-471-48970-2 , p. 14 ( limited online version in Google Book Search - USA )
• Sven Oliver Krumke and Hartmut Noltemeier: Graph theoretical concepts and algorithms . 2nd Edition. Vieweg-Teubner 2009. ISBN 978-3-8348-0629-1 . P. 61

Web links

• Eric W. Weisstein : Chordal Graph . In: MathWorld (English).

Individual evidence

1. ↑ i11www.iti.kit.edu (PDF)