What is the name of this graph operation? (creating $k$ connected copies)

150 Views Asked by At

I'm looking for the name of this natural graph operation, which is kinda similar to Cartesian product, but not quite, as the copies of the graphs are not fully connected.

Instead, it creates a $k$ copies of the graphs and connects vertex $u$ from some copy to vertex $v$ in (different or similar) another copy iff $u,v$ were connected in the first place.

Formally:

Denote: $[k]=\{1,2,\ldots, k\}$, then

$$Dup(G,k) = (\cup\{V_i|i\in [k]\}, \cup \{E_{i,j}\ | i,j\in [k] \})$$

Where $$V_i=\{v_i|v\in V\}, E_{i,j}=\{(u_i,v_j)|(u,v)\in E\}$$

What is the name of the operation $Dup$?

1

There are 1 best solutions below

2
On BEST ANSWER

If I'm understanding your description correctly, the vertex set of your graph construction is $V(G)\times [k]$. The copies of $v$ are $v_1=(v,1),v_2=(v,2), \ldots, v_k=(v,k)$. Vertices $u_i$ and $v_j$ are adjacent if and only if $u$ and $v$ are adjacent in $G$.

If I'm correct and we suppose that $V(\overline{K_k})=V(K_k)=[k]$, then this looks like the union of the $G\Box \overline{K_k}$ and $G\times K_k$. In other words, the vertex set is $V(G)\times [k]=V(G\Box \overline{K_k})=V(G\times K_k)$ and the edge set is $E(G\Box \overline{K_k})\cup E(G\times K_k).$ $G\Box \overline{K_k}$ consists of $k$ copies of $G$ and $G\times K_k$ contains all of the edges between the $k$ different copies of $G$. Beyond this, I don't know a name for the construction.

It is almost the strong product of $G$ and $K_k$, but the strong product would also have an edge between $(u,v)$ and $(u,v')$ as well.