Is there a name for Chain of complete bipartite graphs?

90 Views Asked by At

In a Complete k-partite graph there are K disjoint set $V_{k}$ of vertices and each vertex $u\in V_{k}$ is connected to $v \in V_{t} \;\forall v\in V_{t} \;\forall t\neq k$ and vertices in $V_{k}$ don't have edges between them. But what if every vertex in $V_{i}$ is connected with every vertex in $V_{i+1}$ like a chain of complete bipartite graphs. I think the the entire chain is still a k-partite graph, but it is not complete. Is there a name of such graphs ?

I am not getting much resources on this type of graph. May be I am searching with a wrong name.

1

There are 1 best solutions below

0
On

The concept you're looking for is 'blow-up'.

A blow-up of a graph $G$ is created by replacing each vertex of $G$ by a number of copies of that vertex, where copies of vertices are adjacent if and only if the original vertices were adjacent. Each vertex need not have the same number of copies (but when they do we might call the blow-up 'balanced'). Another way to think about this is like you do: replace each edge of $G$ with the appropriately sized complete bipartite graph.

You are specifically thinking of a blow-up of a path, but you can have blow-ups of any graph. In particular, any complete $k$-partite graph is a blow-up of $K_k$.