# How to glue some isomorphic graphs to a common vertex or a vertex set

I have some isomorphic graphs (in fact, non-isomorphic graphs are also possible), and I want to glue them to a vertex. (Note that here this vertex is a cut vertex). Strictly speaking, two graphs $$G_1$$ with distinguished vertex $$v_1$$ and $$G_2$$ with distinguished vertex $$v_2$$, is formed by identifying vertices( gluing vertices) $$v_1$$ and $$v_2$$ that is, the vertices $$v_1$$ and $$v_2$$ are replaced by a single vertex $$v$$ adjacent to the same vertices in $$G_1$$ as $$v_1$$ and the same vertices in $$G_2$$ as $$v_2$$. If it is not necessary $$v_1$$ or $$v_2$$ may not be specified.

For example, as shown in the figure below, four $$K_4$$ are glued together on a vertex $$u$$. I am not sure if there is a function in mathematica that can do this quickly.

Sagemath seems to be relatively easy with built-in function merge_vertices.

g=graphs.CompleteGraph(4)
I = g.disjoint_union(g)
I = I.disjoint_union(g)
I.relabel()
I.plot()
I.merge_vertices([1,7,8])
I.relabel()
I.plot()


Of course, this problem can be extended, that is, two graphs can be glued together on a subgraph.

GraphDisjointUnion can get the disjoint union of several isomorphic graphs, but it is far from my requirement

This is how I would do it with my IGraph/M package:

We start with $$K_4$$:

g = CompleteGraph[4];


Make 5 copies and create the disjoint union:

bg = IGDisjointUnion[ConstantArray[g, 5]]


Unlike GraphDisjointUnion, IGDisjointUnion preserves the correspondence between the vertices of the original graphs and the new graph. The vertices will be named as {graphIndex, originalName}, where graphIndex is the index of the graph in the input list and originalName is the original vertex name.

Let us contract vertices which had the name 1 in the original $$K_4$$:

IGVertexContract[
bg,
{Cases[VertexList[bg], {_, 1}]}
]


Glue them together on the 1-2 subgraph, i.e. contract both 1s and 2s:

IGVertexContract[
bg,
{Cases[VertexList[bg], {_, 1}], Cases[VertexList[bg], {_, 2}]}
]


Here you may also use the built-in VertexContract instead of IGVertexContract. The advantage of IGVertexContract is that: (1) It provides an unambiguous way to specify vertices even when vertex names are lists (2) It can simultaneously contract multiple sets of vertices. VertexContract did not do this before version 12.1, despite what the documentation seemed to suggest.

• If we have two graphs that are not isomorphic, the function IGVertexContract fails. Commented Dec 30, 2021 at 11:20
• @licheng I can't comment on that without a reproducible example. Commented Dec 30, 2021 at 14:37
• Thanks! I'm thinking of creating a new question. Commented Dec 31, 2021 at 0:05