Hypergraph - Terminology

Terminology

Because hypergraph links can have any cardinality, there are several notions of the concept of a subgraph, called subhypergraphs, partial hypergraphs and section hypergraphs.

Let be the hypergraph consisting of vertices

and having edge set

where and are the index sets of the vertices and edges respectively.

A subhypergraph is a hypergraph with some vertices removed. Formally, the subhypergraph induced by a subset of is defined as

$H_A=\left(A, \lbrace e_i \cap A | e_i \cap A \neq \varnothing \rbrace \right).$

The partial hypergraph is a hypergraph with some edges removed. Given a subset of the edge index set, the partial hypergraph generated by is the hypergraph

Given a subset, the section hypergraph is the partial hypergraph

$H \times A = \left(A, \lbrace e_i | i\in I_e, e_i \subseteq A \rbrace \right).$

The dual of is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by and whose edges are given by where

When a notion of equality is properly defined, as done below, the operation of taking the dual of a hypergraph is an involution, i.e.,

A connected graph G with the same vertex set as a connected hypergraph H is a host graph for H if every hyperedge of H induces a connected subgraph in G. For a disconnected hypergraph H, G is a host graph if there is a bijection between the connected components of G and of H, such that each connected component G' of G is a host of the corresponding H'.

A hypergraph is bipartite if and only if its vertices can be partitioned into two classes U and V in such a way that each hyperedge contains at least one vertex from both classes.

The primal graph of a hypergraph is the graph with the same vertices of the hypergraph, and edges between all pairs of vertices contained in the same hyperedge. The primal graph is sometimes also known as the Gaifman graph of the hypergraph.