Is there a name for this type of graph that generalizes bipartite to general hierarchies?

65 Views Asked by At

Bipartite graphs have the property that there can only be edges between two subsets ("layers" as they usually depicted) of nodes. I am interested in the generalization of this to multiple layers, such that edges can only go between successive layers with no "skip connections". Thus, the graph is hierarchical with a well-defined hierarchical structure. Another way to think of these graphs is that they are exactly the type of graph that defines a neural network. Is there a name for this family of graphs?

Here is an attempt to formalize this, but it may not be perfect: A graph $G=(V,E)$ belongs to my family if $V$ can be partitioned into $k$ sets $V_i$, such that for every $(u,v)\in E$ there exists an $i$ such that $u\in V_i$ and $v\in V_{i+1}$.

Note: I am familiar with the concept of $k$-partite graphs, and this is not the right generalization. A complete $k$-partite graph does not have this hierarchical property.

1

There are 1 best solutions below

0
On

This is sometimes called a graded graph. E.g., in this paper:

A graph is said to be graded if its vertices are divided into levels numbered by integers, so that the endpoints of any edge lie on consecutive levels.

The formal definition given in the paper:

a graded graph is a triple $(P, \rho, E)$ where

  1. $P$ is a discrete set of vertices,
  2. $\rho \colon P \to \mathbb Z$ is a rank function,
  3. $E$ is a multiset of arcs/edges $(x,y)$ where $\rho(y) = \rho(x)+1$.