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.


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$?

  • $\begingroup$ @Axoren - [k]={1,2,…,k}. Duplicate sounds about right, but this doesn't really describe how the copies of the graphs are connected. Have you seen it in use somewhere? $\endgroup$
    – R B
    Jan 18, 2015 at 15:13
  • $\begingroup$ No, I haven't. Where have you seen it? $\endgroup$
    – Axoren
    Jan 18, 2015 at 15:14
  • $\begingroup$ @Axoren- I haven't, and I don't want to reinvent the wheel, so I'm asking what is this operation known as. $\endgroup$
    – R B
    Jan 18, 2015 at 15:15
  • $\begingroup$ If that's the case, we can simplify your construction of it a bit. Since it looks like $G$ is an ordered graph. (If it was not, you could not index the vertices of $G$.) $$Dup(G, k) = (\{v_i\ |\ v_i \in V, i \le k\}, \{(v_i, v_j)\ |\ (v_i, v_j) \in E \land i,j \le k\})$$ $\endgroup$
    – Axoren
    Jan 18, 2015 at 15:30
  • $\begingroup$ As for a name for it, it would just be the "left-most" ordered sub-graph of order $k$. $\endgroup$
    – Axoren
    Jan 18, 2015 at 15:33

1 Answer 1


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.

  • $\begingroup$ I'm not sure we're on the same page :). Every vertex $v$ in the graph $G$ now has $k$ copies, and each copy $v_i$ of a vertex $v$ will be connected to each copy $u_j$ of a vertex $u$ if $u$ and $v$ were connected. By $V_i$ I simply mean a copy of $V$ with a label $i$ (where $i\in [k]$) attached to each vertex. $\endgroup$
    – R B
    Jan 18, 2015 at 18:17
  • $\begingroup$ Yes. It is customary to write the vertex set of a graph product as a Cartesian product of sets, so the copies of a vertex are actually ordered pairs. As an ordered pair, your $v_i$ is written as $(v,i)$. I've rewritten the post to reflect this. $\endgroup$
    – Randy E
    Jan 18, 2015 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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