Laplacian Matrix

The Laplacian matrix, sometimes also called the admittance matrix (Cvetković et al. 1998, Babić et al. 2002) or Kirchhoff matrix, of a graph , where  is an undirected, unweighted graph without graph loops  or multiple edges from one node to another,  is the vertex set, , and  is the edge set, is an  symmetric matrix with one row and column for each node defined by

(1)

where  is the degree matrix, which is the diagonal matrix formed from the vertex degrees and  is the adjacency matrix. The diagonal elements  of  are therefore equal the degree of vertex  and off-diagonal elements  are  if vertex  is adjacent to  and 0 otherwise.

The Laplacian matrix of a graph is implemented in the Wolfram Language as KirchhoffMatrix[g].

A normalized version of the Laplacian matrix, denoted , is similarly defined by

{1 if i=j and d_j!=0; -1/(sqrt(d_id_j)) if i and j are adjacent; 0 otherwise " src="https://mathworld.wolfram.com/images/equations/LaplacianMatrix/NumberedEquation2.svg" style="height:111px; width:299px" />

(2)

(Chung 1997, p. 2).

The Laplacian matrix is a discrete analog of the Laplacian operator in multivariable calculus and serves a similar purpose by measuring to what extent a graph differs at one vertex from its values at nearby vertices. The Laplacian matrix arises in the analysis of random walks and electrical networks on graphs (Doyle and Snell 1984), and in particular in the computation of resistance distances. The Laplacian also appears in the matrix tree theorem.

---

REFERENCES

Akban, S. and Oboudi, M. R. "On the Edge Cover Polynomial of a Graph." Europ. J. Combin. 34, 297-321, 2013.

Babić, D.; Klein, D. J.; Lukovits, I.; Nikolić, S.; and Trinajstić, N. "Resistance-Distance Matrix: A Computational Algorithm and Its Applications." Int. J. Quant. Chem. 90, 166-176, 2002.

Bendito, E.; Carmona, A.; and Encinas, A. M. "Shortest Paths in Distance-Regular Graphs." Europ. J. Combin. 21, 153-166, 2000.

Chung, F. R. K. Spectral Graph Theory. Providence, RI: Amer. Math. Soc., 1997.

Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.

Demmel, J. "CS 267: Notes for Lecture 23, April 9, 1999.

Graph Partitioning, Part 2." http://www.cs.berkeley.edu/~demmel/cs267/lecture20/lecture20.html.

Devillers, J. and A. T. Balaban (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, pp. 74-75, 2000.

Doyle, P. G. and Snell, L. Random Walks and Electric Networks. Washington, DC: Math. Assoc. Amer., 1984.

Mohar, B. "The Laplacian Spectrum of Graphs." In Graph Theory, Combinatorics, and Applications, Vol. 2: Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs held at Western Michigan University, Kalamazoo, Michigan, May 30-June 3, 1988 

(Ed. Y. Alavi, G. Chartrand, O. R. Oellermann, and A. J. Schwenk). New York: Wiley, pp. 871-898, 1991.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم الشؤون الطبية يقدم الخدمات الصحية والعلاجية لزائري مدينة سامراء

العتبة العباسية المقدسة تقدم خدماتها لزائري مرقد الإمامين العسكريين (عليهما السلام) في سامراء

المجمَع العلمي ووفد وزارة التربية يبحثان سبل التعاون المشترك

قسم الشؤون الفكرية يصدر العدد 192 من مجلة الرياحين للأطفال

المزيد

الآخبار الصحية

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

الآخبار التكنلوجية

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength