2
$\begingroup$

Let $S$ be a finite sequence of positive integers of length $n$. Let $G$ be a finite graph containing $n$ not null edgeless subgraphs. Call these subgraphs $G_0,G_1,\ldots,G_{n-1}$ and let each $G_i$ have order $S_i$. Define the edges of $G$ such that, for all $i>0$, $G_i$ forms a complete bipartite graph with $G_{i-1}$. $G$ contains no other edges.

Does this graph have a name? I would appreciate any suggestions for a name if none already exists.

  • 0
    It is always biparite for n > 1.2011-01-26

1 Answers 1

4

This is known as a "layered graph". If all $S_i$ are equal then it's a "trellis diagram", an object used by the Viterbi decoding algorithm (which is a fancy name for dynamic programming).

  • 0
    If the edges are directed according to $i$, then this is the minimum transitive reduction of a "graded poset" where $i$ is the rank function.2011-01-27