Hypertree

File:Hypertree.svg

A hypertree (blue vertices and yellow hyperedges) and its host tree (red)

In the mathematical field of graph theory, a hypergraph Template:Mvar is called a hypertree if it admits a host graph Template:Mvar such that Template:Mvar is a tree. In other words, Template:Mvar is a hypertree if there exists a tree Template:Mvar such that every hyperedge of Template:Mvar is the set of vertices of a connected subtree of Template:Mvar. Hypertrees have also been called arboreal hypergraphs or tree hypergraphs.

Every tree Template:Mvar is itself a hypertree: Template:Mvar itself can be used as the host graph, and every edge of Template:Mvar is a subtree of this host graph. Therefore, hypertrees may be seen as a generalization of the notion of a tree for hypergraphs. They include the connected Berge-acyclic hypergraphs, which have also been used as a (different) generalization of trees for hypergraphs.

Properties

Every hypertree has the Helly property (2-Helly property): if a subset Template:Mvar of its hyperedges has the property that every two hyperedges in Template:Mvar have a nonempty intersection, then Template:Mvar itself has a nonempty intersection (a vertex that belongs to all hyperedges in Template:Mvar).

By results of Duchet, Flament and Slater hypertrees may be equivalently characterized in the following ways.

• A hypergraph Template:Mvar is a hypertree if and only if it has the Helly property and its line graph is a chordal graph.
• A hypergraph Template:Mvar is a hypertree if and only if its dual hypergraph Template:Mvar is conformal and the 2-section graph of Template:Mvar is chordal.
• A hypergraph is a hypertree if and only if its dual hypergraph is alpha-acyclic in the sense of Fagin.

It is possible to recognize hypertrees (as duals of alpha-acyclic hypergraphs) in linear time.Template:Sfnp The exact cover problem (finding a set of non-overlapping hyperedges that covers all the vertices) is solvable in polynomial time for hypertrees but remains NP-complete for alpha-acyclic hypergraphs.

See also

• Dually chordal graph, a graph whose maximal cliques form a hypertree

References

• .
• .
• .
• .
• .
• .
• .
• .