0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ What do you mean by "calculate"? $\endgroup$
    – Felix Goldberg
    Commented Apr 12, 2014 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
    Commented Apr 12, 2014 at 8:17

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you for your help. Reference? $\endgroup$
    – Supriyo
    Commented Apr 12, 2014 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
    Commented Apr 12, 2014 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$
    – Delio Mugnolo
    Commented Apr 13, 2014 at 5:24
  • $\begingroup$ How much work has been done to find out the Laplacian for a graph with loop? $\endgroup$
    – Supriyo
    Commented Apr 13, 2014 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$
    – Delio Mugnolo
    Commented Apr 13, 2014 at 10:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .