# Is there a name for this operation on graphs - e.g. duplication, Kronecker product of graphs?

I am revising a paper where one of the operations performed on a undirected graph with no loops, is to take each vertex, and split it into two vertices, and take each edge and replace it with 4 edges: e.g. vertices a and b with edge (a,b) become vertices -a, +a, -b, +b, with edges (-a,-b), (-a,+b), (+a,-b), (+a,+b). A corresponding operation on the adjacency matrix is a Kronecker product with the matrix [[1,1],[1,1]] (the 2 x 2 matrix containing only ones.) The obvious generalization is to replace the 2 x 2 all-ones matrix with an arbitrary symmetric {0,1} matrix.

Are these operations well known? Is there a well known name for them?

Its the lexicographic product of the empty graph on two vertices by your original graph. (The terminology for lexicographic product is a bit confused - it's not commutative and there are two schools of thought about which graph should go first.)

• Thanks. I checked against MathWorld, which calls this a "double graph", but then claims that this is the lexicographic product of the original graph and K_2, which is wrong. Aug 31, 2013 at 13:33
• There is a reasonably standard term "doubling a vertex", and if you double each vertex you get a lexicographic product. Aug 31, 2013 at 13:37
• I have found two references. Indulal, G. (2007). Studies on the spectrum and the energy of graphs. (Doctoral dissertation, Cochin University of Science and Technology). Definition 30, page 16. Emanuele Munarini, Claudio Perelli Cippo, Andrea Scagliola, Norma Zagaglia Salvi, Double graphs, Discrete Mathematics, Volume 308, Issues 2–3, 6 February 2008, Pages 242-254 Sep 1, 2013 at 3:17
• Sorry, I am still learning how to edit comments on this web site. The system won't let me edit my previous comment. So here it is again. I have found two references. * Indulal, G. (2007). Studies on the spectrum and the energy of graphs. (Doctoral dissertation, Cochin University of Science and Technology). Definition 30, page 16. * Emanuele Munarini, Claudio Perelli Cippo, Andrea Scagliola, Norma Zagaglia Salvi, Double graphs, Discrete Mathematics, Volume 308, Issues 2–3, 6 February 2008, Pages 242-254 Sep 1, 2013 at 3:24
• OK, I give up. The documentation says that the system uses markdown, so I can create linebreaks and lists, but when I actually do what it says to do, it does not work. Sep 1, 2013 at 3:27

I have found two references.

• Indulal, G. (2007). Studies on the spectrum and the energy of graphs.in/jspui/bitstream/purl/2868/3/Dyuthi-T0865.pdf) (Doctoral dissertation, Cochin University of Science and Technology). Definition 30, page 16.

• Emanuele Munarini, Claudio Perelli Cippo, Andrea Scagliola, Norma Zagaglia Salvi, Double graphs, Discrete Mathematics, Volume 308, Issues 2–3, 6 February 2008, Pages 242-254