# Name this graph

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.

-
This looks like a special case of an $n$-partite graph. – Rahul Jan 26 '11 at 19:19
In fact, the graph is always bipartite. – Yuval Filmus Jan 26 '11 at 21:11
It is always biparite for $n > 1$. – ThomasMcLeod Jan 26 '11 at 22:05

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).
I described the complete version. So "complete layered graph" is the name. This is the undirected graph of strict weak ordering, where the subgraphs $G_i$ are the equivalence classes of the ordering. – ThomasMcLeod Jan 27 '11 at 0:25
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. – Mitch Jan 27 '11 at 15:35