Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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

1 Answer 1

up vote 4 down vote accepted

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).

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.