Hypertree

From Wikipedia, the free encyclopedia
Jump to: navigation, search

A hypergraph H is called a hypertree in [1](arboreal hypergraph in,[2] tree hypergraph in [3]) if it admits a host graph T such that T is a tree, in other words if there exists a tree T such that every hyperedge of H induces a subtree in T.

Since a tree is a hypertree, hypertrees may be seen as a generalization of the notion of a tree for hypergraphs. Any hypertree is isomorphic to some family of subtrees of a tree.[4]

Properties[edit]

A hypertree has the Helly property (2-Helly property), i.e., if any two hyperedges from a subset of its hyperedges have a common vertex, then all hyperedges of the subset have a common vertex.[5]

By results of Duchet, Flament and Slater (see e.g.[6]), a hypergraph is a hypertree if and only if it has the Helly property and its line graph is chordal if and only if its dual hypergraph is conformal and chordal.[7]

Thus, a hypergraph is a hypertree if and only if its dual hypergraph is alpha-acyclic (in the sense of Fagin et al.)

References[edit]

References[edit]

  • Berge, Claude (1989), Hypergraphs, North Holland .
  • Brandstädt, Andreas; Dragan, Feodor; Chepoi, Vitaly; Voloshin (1998), "Dually Chordal Graphs", SIAM Journal on Discrete Mathematics 11: 437–455 .
  • 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 .
  • McKee, T. A.; McMorris, F.R. (1999), Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-430-3 .
  • Voloshin, Vitaly (2002), Coloring Mixed Hypergraphs, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-8218-2812-6 .