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
    This looks like a special case of an [$n$-partite graph](http://mathworld.wolfram.com/k-PartiteGraph.html).2011-01-26
  • 0
    In fact, the graph is always bipartite.2011-01-26
  • 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
    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.2011-01-27
  • 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