Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
What do you mean by "calculate"? –  Felix Goldberg Apr 12 at 8:01
    
@FelixGoldberg I want to write down the Laplacian matrix for a graph with positive and negative weights in an explicit manner. –  Dutta Apr 12 at 8:17

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Thank you for your help. Reference? –  Dutta Apr 12 at 11:23
    
It is working for graphs without loops but there are some obstacle it you add loop in the graph. –  Dutta Apr 12 at 12:29
    
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. –  Delio Mugnolo Apr 13 at 5:24
    
How much work has been done to find out the Laplacian for a graph with loop? –  Dutta Apr 13 at 5:53
    
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/… –  Delio Mugnolo Apr 13 at 10:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.