1
$\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 Answers 2

3
$\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.)

$\endgroup$
6
  • $\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, 2013 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$ Aug 31, 2013 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, 2013 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, 2013 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, 2013 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

$\endgroup$

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.