Hypertree
In the mathematical field of graph theory, a hypergraph  is called a hypertree if it admits a host graph  such that  is a tree. In other words,  is a hypertree if there exists a tree  such that every hyperedge of  is the set of vertices of a connected subtree of . Hypertrees have also been called arboreal hypergraphs or tree hypergraphs. Every tree  is itself a hypertree:  itself can be used as the host graph, and every edge of  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  of its hyperedges has the property that every two hyperedges in  have a nonempty intersection, then  itself has a nonempty intersection (a vertex that belongs to all hyperedges in ). By results of Duchet, Flament and Slater hypertrees may be equivalently characterized in the following ways. A hypergraph  is a hypertree if and only if it has the Helly property and its line graph is a chordal graph. A hypergraph  is a hypertree if and only if its dual hypergraph  is conformal and the 2-section graph of  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. 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

Notes

References

. . . . . . . . Hypergraphs
Trees (graph theory)