What do you call a graph that has vertex groups

directed graphsgraph theoryterminology

I was wondering what to call a graph that can have a group of vertices as one vertex while at the same time allowing individual vertices in the group to be linked to other vertices in the graph. Here is a figure to illustrate:

example graph

In the example figure, note the following:

  • we cannot have 2 edges from a and b to c. The semantics here is: the (a,b) group has to be linked to C and not a and b individually.
  • we can have the group act as one vertex ((d,e) -> f) and we can have a subset of the group to act as one vertex as well (c -> e)
  • let's assume we are only dealing with a directed graph
  • let's assume the group cannot have an inward edge (the destination of every edge is a single vertex)

This cannot be represented as a hypergraph because the vertices inside a group are never linked together.

What I have in mind: we can look at this graph as a directed graph that can have vertex groups (including those that with 1 vertex). So every vertex becomes a vertex group, and then the notation would be: G(V, S, E). V is the set of individual vertices, S is the set of vertex groups defined over V, and E is the set of edges connecting v -> w s.t. v and w are in S. Does this seem sound?

Any pointers would be appreciated.

Best Answer

This is called a directed hypergraph.

Each edge of a directed hypergraph is a pair of subsets of the vertex sets: a "tail subset" and a "head subset". We think of the hyperedge as going from the tail subset to the head subset.

In the example you drew, the three edges are

  • an edge with tail $\{a,b\}$ and head $\{c\}$
  • an edge with tail $\{c\}$ and head $\{d\}$
  • an edge with tail $\{d,e\}$ and head $\{f\}$.
Related Question