Given a connected graph $G$ with $n$ vertices and given a tuple of $\mathbf{m} = \{m_1,m_2,…,m_n\}$ non-negative integers, we form a new graph $G(\mathbf m)$ by considering the complete graph $K_{m_i}$ for each vertex i and 'join' two of such complete graphs if the corresponding vertices are adjacent. By joining of two graphs $G_1$ and $G_2$, I mean introducing edges from all the vertices of $G_1$ to all the vertices of $G_2$ and vice versa, keeping the original edges as it is.
My question is suppose $G_1$ and $G_2$ are graphs with the same number of vertices and suppose $G_1(\mathbf m)\cong G_2(\mathbf m)$ for some $\mathbf m$ does it implies that $G_1 \cong G_2$?
If the number of vertices is not the same, then this is not true. I have checked with some examples.
Thanks for your valuable time.
Thanks a lot
Best Answer
If I understand what you're saying, this is a counterexample.
Let $G_1$ be a graph with vertices $x_1,x_2,x_3,x_4,x_5$ and edges $x_1x_2,x_3x_4,x_1x_5,x_2x_5,x_3x_5,x_4x_5$.
Let $G_2$ be a graph with vertices $x_1,x_2,x_3,x_4,x_5$ and edges $x_2x_3,x_2x_4,x_3x_4,x_1x_5,x_2x_5,x_3x_5,x_4x_5$.
$G_1$ and $G_2$ are connected graphs of order $5$, and they are not isomorphic.
If $\mathbf m=(2,1,1,1,1)$, then $G_1(\mathbf m)\cong G_2(\mathbf m)$.
More generally, if $\mathbf m=(m_1,m_2,m_3,m_4,m_5)$ where $m_1=m_3+m_4$, then $G_1(\mathbf m)\cong G_1(\mathbf m)$.