I am trying to calculate the Laplacian and Adjacency matrix of a graphs for positive and negative weights. If a graph be simple with only non-negative weight it is easier. But in my graph I have some negative weights and loops.

Please give me some references and hints if available.

Thank you for your help.

  • $\begingroup$ What do you mean by "calculate"? $\endgroup$ Apr 12 '14 at 8:01
  • $\begingroup$ @FelixGoldberg I want to write down the Laplacian matrix for a graph with positive and negative weights in an explicit manner. $\endgroup$
    – Supriyo
    Apr 12 '14 at 8:17

The most natural definition of Laplacian matrix is to me $\mathcal L=\mathcal I\mathcal I^T$, where $\mathcal I$ is the incidence matrix of an arbitrary orientation of the graph; or more generally $\mathcal L=\mathcal I\mathcal M\mathcal I^T$, where $\mathcal M$ is the diagonal matrix whose entries are the edge weights. Now, the very same definition can be used to define a Laplacian matrix with general (i.e., also negative) weights.

  • $\begingroup$ Thank you for your help. Reference? $\endgroup$
    – Supriyo
    Apr 12 '14 at 11:23
  • $\begingroup$ It is working for graphs without loops but there are some obstacle it you add loop in the graph. $\endgroup$
    – Supriyo
    Apr 12 '14 at 12:29
  • $\begingroup$ Concerning your first question: What do you mean by "references"? It is a definition. But a standard one, if you mean this: Take a look in Biggs' book, Godsil-Royle's book, Mohar's surveys, etc. Yes, loops are generally very problematic when it comes to defining Laplacians, even if no weights are assigned. $\endgroup$ Apr 13 '14 at 5:24
  • $\begingroup$ How much work has been done to find out the Laplacian for a graph with loop? $\endgroup$
    – Supriyo
    Apr 13 '14 at 5:53
  • $\begingroup$ I am sorry, but I do not understand your question yet. The Laplacian is just a matrix defined in a certain way, and its introduction goes back to Kirchhoff. At a certain point in the history (around 1970) people started noticing this matrix was tightly connected with the "usual" Laplacian on domains. If you are interested in some historical remarks, you can take a look at the notes at the end of Chapter 2 of this monograph: uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.010/mugnolo/… $\endgroup$ Apr 13 '14 at 10:15

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.