0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Penguian Aug 31 '13 at 13:33
  • $\begingroup$ There is a reasonably standard term "doubling a vertex", and if you double each vertex you get a lexicographic product. $\endgroup$ – Chris Godsil Aug 31 '13 at 13:37
  • $\begingroup$ 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 $\endgroup$ – Penguian Sep 1 '13 at 3:17
  • $\begingroup$ 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 $\endgroup$ – Penguian Sep 1 '13 at 3:24
  • $\begingroup$ 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. $\endgroup$ – Penguian Sep 1 '13 at 3:27
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.