3
$\begingroup$

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.

enter image description here

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

enter image description here

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

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

$\endgroup$

1 Answer 1

3
$\begingroup$

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}]}
]

enter image description here

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}]}
 ]

enter image description here

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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