In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix.. (Theory) In Chapter1, we review the basic de nitions, notations, and results in graph theory and spectral graph theory. /ColorSpace 3 0 R /Pattern 2 0 R /ExtGState 1 0 R /Parent 70 0 R /D [41 0 R /XYZ 28.346 272.126 null] 16 0 obj /Rect [305.662 8.966 312.636 18.431] And the theory of association schemes and coherent con- 2020. 49 0 obj << << /S /GoTo /D [41 0 R /Fit ] >> >> endobj In this lecture we discuss Spectral Graph Theory, Conductance, Cheeger’s Inequality, and Spectral Cluster-ing. /Rect [326.355 8.966 339.307 18.431] << /S /GoTo /D (Outline0.8) >> This problem has been shown to be NP-complete. 46 0 obj << The main objective of spectral graph theory is to relate properties of graphs with the eigenvalues and eigenvectors (spectral properties) of associated matrices. Tables of Graph Spectra Biblgraphy. 39 0 obj /Trans << /S /R >> 23 0 obj @��DoI$�$��`�Q�z0�(4�gp>9~��7����ፇ�lC'��B��#�A�r�4p�Ƣ (Open Problems) /Type /Annot At first glance it might be surprising that such connections exist at all. Spectral graph theory studies connections between combinatorial properties of graphs and the eigenvalues of matrices associated to the graph, such as the adjacency matrix and the Laplacian matrix. /Subtype/Link/A<> << /S /GoTo /D (Outline0.2) >> endobj Spectral graph theory concerns the connection and interplay between the subjects of graph theory and linear algebra. /Border[0 0 0]/H/N/C[.5 .5 .5] 45 0 obj << /A << /S /GoTo /D (Navigation1) >> /Type /Annot stream 58 0 obj << /Type /Annot (References) endobj /Rect [267.264 8.966 274.238 18.431] S���r�/STz�|eU���–Jڤ"�W�t� m�H�bt�o�#�H}l��͂^��./����g��Dz?����7^���m���d���-g�|�w����6�����)�U�,]Ut�qLYH���l��DE����ȕB,�\��A��i��L�S��C�}�B���x�J�j��7'������+����J����X�R��"�YA|���ݖ=�f=>�ŖX�n����O޵�������ns�C�b��S'�Y�$��-��F^ې���6�?=t�F�a19���I�.X�5��11i���ҧ�R�N�S�PD�f�����3���k2h������=��em[Blj�%F-8ػ-�.�{&�せ�;O��{�=��Y��c����e��u���Z�Y�1Na����b�Q>�R u��KO���s�Mj�E��H��R���'E���I��o8*Y���Sh��e�"")�hb#�.����)�}��|}���[�Bh�}?��X�2!�[email protected]�u�>���h��������.���S��Z���{����x�v8�)1�e3�Ιdc��A������'b[2V�%m��S��M{V�����ط��H�QP�w�����gf=�Bj�)�oE%p�����O�>. Appendix. /Subtype /Link /Border[0 0 0]/H/N/C[.5 .5 .5] >> endobj /Type /Annot 51 0 obj << /Border[0 0 0]/H/N/C[.5 .5 .5] Spectral Lower Bounds on the I/O Complexity of Computation Graphs. >> endobj Some Additional Results. /Rect [274.01 8.966 280.984 18.431] Introduction to Spectral Graph Theory Spectral graph theory is the study of a graph through the properties of the eigenvalues and eigenvectors of its associated Laplacian matrix. More in particular, spectral graph the-ory studies the relation between graph properties and the spectrum of the adjacency matrix or Laplace matrix. /Border[0 0 0]/H/N/C[1 0 0] /Border[0 0 0]/H/N/C[.5 .5 .5] 41 0 obj << >> endobj /Rect [230.631 8.966 238.601 18.431] 104 0 obj << >> endobj Due to the recent discovery of very fast solvers for these equations, they are also becoming increasingly useful in combinatorial opti- The general theme is then, firstly, to compute or estimate the eigenvalues of such matrices, and secondly, to relate the eigenvalues to structural properties of graphs. Some of its loveliest applications concern facts that are, in principle, purely graph-theoretic or combinatorial. 48 0 obj << /Border[0 0 0]/H/N/C[.5 .5 .5] /Rect [346.052 8.966 354.022 18.431] /Border[0 0 0]/H/N/C[.5 .5 .5] 32 0 obj 40 0 obj >> endobj Our approach is based on defining scaling using the the graph analogue of the Fourier domain, namely the spectral decomposition of the discrete graph Laplacian $Ł$. 56 0 obj << Our applications will include structural characterizations of the graph, interlacing >> endobj In the following, we use G = (V;E) to represent an undirected n-vertex graph with no self-loops, and write V = f1;:::;ng, with the degree of vertex idenoted d i. In the early days, matrix theory and linear algebra … /Subtype /Link x��VIO1��W�cr��r�R[�*QBnU0�@�L����3�'%��x�����M�(|е���p�F��МX��N��T0�l(��H���Gq��C�mZ�B�cm����= >}\0��ƈT�zp � q�b!ᬂ{�*�p���U�e ��F�(Ĩ�Ğ���kY ݏ�mp+��$��瓔�95Z�O��� Lecture 4 { Spectral Graph Theory Instructors: Geelon So, Nakul Verma Scribes: Jonathan Terry So far, we have studied k-means clustering for nding nice, convex clusters which conform to the standard notion of what a cluster looks like: separated ball-like congregations in space. 6 A BRIEF INTRODUCTION TO SPECTRAL GRAPH THEORY A tree is a graph that has no cycles. 27 0 obj /D [41 0 R /XYZ 334.488 0 null] /A << /S /GoTo /D (Navigation1) >> endobj /Resources 62 0 R 28 0 obj 54 0 obj << /Border[0 0 0]/H/N/C[1 0 0] In the summer of 2006, the daunting task of revision finally but surely got started. /Border[0 0 0]/H/N/C[.5 .5 .5] As it turns out, the spectral perspective is a powerful tool. /Subtype /Link << /S /GoTo /D (Outline0.4) >> 11 0 obj /Font << /F18 65 0 R /F16 66 0 R /F17 67 0 R >> 36 0 obj 53 0 obj << Lecture 11: Introduction to Spectral Graph Theory Rajat Mittal IIT Kanpur We will start spectral graph theory from these lecture notes. endobj To help the reader reconstruct the ow of my courses, I give three orders that I have used for the material: put orders here There are many terri c books on Spectral Graph Theory. Important early work was done by social scientists: sociologists, /A << /S /GoTo /D (Navigation2) >> /Type /Annot /Rect [352.03 8.966 360.996 18.431] 44 0 obj << Spectral graph theory Economics is a social science that tries to understand how supply and demand control the allocation of limited resources. >> endobj << /S /GoTo /D (Outline0.1) >> 11.1 Spectral Graph Theory In the eld of spectral graph theory we relate combinatorial properties of graphs to their algebraic properties. /Type /Annot /Rect [339.078 8.966 348.045 18.431] >> endobj Spectra Techniques in Graph Theory and Combinatories. Spectral graph theory starts by associating matrices to graphs, notably, the adjacency matrix and the laplacian matrix. /Border[0 0 0]/H/N/C[.5 .5 .5] >> endobj The wide range of these topics showcases the power and versatility of the eigenvalue techniques such as interlacing, the common thread that ties these topics together. 43 0 obj << /Rect [283.972 8.966 290.946 18.431] (Homework Problems) Introduction Spectral graph theory has a long history. /Rect [257.302 8.966 264.275 18.431] 42 0 obj << Network science today is a vast multidisciplinary field. /Subtype /Link Some features of the site may not work correctly. %���� However, substantial revision is clearly needed as the list of errata got longer. 12 0 obj /Subtype /Link If M2Cm n The Spectrum and the Group of Automorphisms. /Rect [252.32 8.966 259.294 18.431] It has been found that partitioning a graph based on its spectrum and eigenvectors provides a good Spectral graph theory has applications to the design and analysis of approximation algorithms for graph partitioning problems, to the study of random walks in graph, and to the computational graphs, spectral graph theory, I/O lower bounds ACM Reference Format: Saachi Jain and Matei Zaharia. /Filter /FlateDecode >> endobj Spectral Graph Theory I Appeared as a branch of algebraic graph theory in the 1950s and 1960s. /A << /S /GoTo /D (Navigation1) >> endstream (16.2) This form measures the smoothness of the function x. /Type /Annot /A << /S /GoTo /D (Navigation1) >> play a major role. For instance, star graphs and path graphs are trees. endobj Today, we In this paper, we focus on the connection between the eigenvalues of the Laplacian matrix and graph connectivity. A major effort in modern graph theory focuses on studying the connection between the eigenvalues of the adjacency matrix of a graph, the graph’s spectrum, and its combinatorial properties. We assume that the reader is familiar with ideas from linear algebra and assume limited knowledge in graph theory. /Type /Annot /Subtype/Link/A<> >> endobj x= X i (fT i x)f i The intuition here is that, we rst compute the projection length of xonto f i which is just the inner product xTf i. /A << /S /GoTo /D (Navigation1) >> spectral techniques in solving graph partitioning problems where graph vertices are partitioned into two disjoint sets of similar sizes while the number of edges between the two sets is minimized. /A << /S /GoTo /D (Navigation1) >> (Overview) >> endobj 69 0 obj << 47 0 obj << Spectral graph theory studies how the eigenvalues of the adjacency matrix of a graph, which are purely algebraic quantities, relate to combinatorial properties of the graph. endobj endobj 3.1 Basic de nitions We begin with a brief review of linear algebra. I Early work focused on using the adjacency matrix, which limited initial results to regular graphs. (History) Lectures #11: Spectral Graph Theory, I Tim Roughgarden & Gregory Valiant May 11, 2020 Spectral graph theory is the powerful and beautiful theory that arises from the following question: What properties of a graph are exposed/revealed if we 1) represent the graph as /Type /Annot The Divisor of a Graph. >> endobj D. J. Kelleher Spectral graph theory. Publication: CBMS Regional Conference Series in Mathematics Publication Year: 1997; Volume 92 ISBNs: 978-0-8218-0315-8 (print); 978-1-4704-2452-7 (online) (Applications) /Annots [ 42 0 R 43 0 R 44 0 R 45 0 R 46 0 R 47 0 R 48 0 R 49 0 R 50 0 R 51 0 R 52 0 R 53 0 R 54 0 R 55 0 R 56 0 R 57 0 R 58 0 R 59 0 R 60 0 R 61 0 R ] 24 0 obj Fan R. K. Chung, University of Pennsylvania, Philadelphia, PA. /Subtype /Link << /S /GoTo /D (Outline0.5) >> /Type /Annot /Border[0 0 0]/H/N/C[.5 .5 .5] /Type /Annot /Subtype/Link/A<> /A << /S /GoTo /D (Navigation36) >> There is a root vertex of degree d−1 in Td,R, respectively of degree d in T˜d,R; the pendant vertices lie on a sphere of radius R about the root; the remaining interme- << /S /GoTo /D (Outline0.3) >> 57 0 obj << Spectral graph theory is the study of properties of the Laplacian matrix or adjacency matrix associated with a graph. >> endobj >> endobj /A << /S /GoTo /D (Navigation2) >> For instance, extreme eigenvalues of the Laplacian or adjacency matrix are used for partitioning, community detection, dimension reduction for large data sets, data visualization, and a number of other tasks in data science/machine learning theory. /Type /Annot /Subtype /Link If x= a+ ibis a complex number, then we let x = a ibdenote its conjugate. /Border[0 0 0]/H/N/C[.5 .5 .5] (Linear Algebra Primer) Let x= 1S j Sj 1S j where as usual 1S represents the indicator of S. The quadratic form of Limplies that xT Lx= 0, as all neighboring vertices were assigned the same weight in x. /Border[0 0 0]/H/N/C[.5 .5 .5] /Rect [295.699 8.966 302.673 18.431] 35 0 obj /A << /S /GoTo /D (Navigation3) >> In this paper we introduce this spectral graph wavelet transform and study several of its properties. /Rect [236.608 8.966 246.571 18.431] You are currently offline. /Type /Annot To give just one example, spectral…, The adjacency algebra of a graph, with an application to affine planes, Approximate graph spectral decomposition with the Variational Quantum Eigensolver, Some results on the Laplacian Spread Conjecture, Volume of Seifert representations for graph manifolds and their finite covers, On the spectrum of an equitable quotient matrix and its application, Spectral Graph Analysis with Apache Spark, Spectrum of some arrow-bordered circulant matrix, Geometric Formulation for Discrete Points and its Applications, I ’ ve got 99 vertices but a solution to Conway ’ s problem ain ’ t one, Polaritons and excitons: Hamiltonian design for enhanced coherence, By clicking accept or continuing to use the site, you agree to the terms outlined in our. /Type /Annot 19 0 obj /Type /Annot Spectral graph theory is the interplay between linear algebra and combinatorial graph theory. The focus of spectral graph theory is … >> As it turns out, the spectral perspective is a powerful tool. /Rect [288.954 8.966 295.928 18.431] The common trick we would use to prove stu in spectral graph theory is to decompose the vector into neigenvectors directions. /Rect [244.578 8.966 252.549 18.431] >> endobj /Subtype /Link Spectral graph theory studies how the eigenvalues of the adjacency matrix of a graph, which are purely algebraic quantities, relate to combinatorial properties of the graph. >> endobj /ProcSet [ /PDF /Text ] Since Gis disconnected, we can split it into two sets Sand Ssuch that jE(S;S)j= 0. /Subtype /Link 8 0 obj << /S /GoTo /D (Outline0.6) >> 31 0 obj Speci cally, we will study random walks on an undirected graph G= (V;E), where the time proceeds in unit steps: t= 1;2;:::. 20 0 obj The general theme is then, firstly, to compute or estimate the eigenvalues of such matrices, and secondly, to relate the eigenvalues to structural properties of graphs. /Rect [262.283 8.966 269.257 18.431] Lecture 13: Spectral Graph Theory 13-3 Proof. Semantic Scholar is a free, AI-powered research tool for scientific literature, based at the Allen Institute for AI. endobj Laplace’s equation and its discrete form, the Laplacian matrix, appear ubiquitously in mathematical physics. /Contents 63 0 R 15 0 obj Spectral Graph Theory About this Title. 68 0 obj << stream /Subtype /Link In this paper we begin by introducing basic graph theory terminology. /Border[0 0 0]/H/N/C[.5 .5 .5] Spectral graph theory starts by associating matrices to graphs, notably, the adjacency matrix and the laplacian matrix. 61 0 obj << 59 0 obj << 60 0 obj << /Border[0 0 0]/H/N/C[.5 .5 .5] Techniques from spectral graph theory, linear and multilinear algebra, probability, approximation theory, etc. If x= a+ibis a complex number, then we let x= a ibdenote its conjugate. >> endobj We show that in the fine scale limit, for sufficiently regular g , … endobj Spectral Graph Theory 5 16.3.2 The Laplacian Quadratic Form Matrices and spectral theory also arise in the study of quadratic forms. /Border[0 0 0]/H/N/C[.5 .5 .5] /Subtype /Link /Length 794 /A << /S /GoTo /D (Navigation1) >> 50 0 obj << /Border[0 0 0]/H/N/C[1 0 0] G���&a5�1�S�B}�6�lj[�D��I�Λ&��S��83�b�!�#�t""�b���'�� t�ԫ�nf���B�t�H'��p�m��nY�N2�%~�۽*�m��8s!>�Qю��j��6�9ۥ��~7а��F��|��h ��V�4[��bԦa���zvG�Y�'q�����VԾϒ�K����Έ���Ie��L�k�Q��ΐ�� The most natural quadratic form to associate with a graph is the Laplacian , which is given by xTL Gx = # (a,b)∈E w(a,b)(x(a) −x(b))2. Because the economy is dynamic and constantly changing, economists should take snapshots of economic data at certain points in time and compare it to other fixed-time data sets to understand ORIE 6334 Spectral Graph Theory September 22, 2016 Lecture 11 Lecturer: David P. Williamson Scribe: Pu Yang In today’s lecture we will focus on discrete time random walks on undirected graphs. Algebraic graph theory is the branch of mathematics that studies graphs by using algebraic properties of associated matrices. /Type /Annot >> endobj >> endobj /A << /S /GoTo /D (Navigation1) >> endobj The ongoing research in this field unravels more and more of them. >> Spectral Graph Theory to appear in Handbook of Linear Algebra, second edition, CCR Press Steve Butler Fan Chungy There are many di erent ways to associate a matrix with a graph (an introduction of which can be found in Chapter 28 on Matrices and Graphs). >> endobj We begin with a brief review of linear algebra. 62 0 obj << /Filter /FlateDecode /Subtype/Link/A<> Relations Between Spectral and Structural Properties of Graphs. Then we multiply … Spectral graph drawing: Tutte justification Gives for all i λsmall says x(i) near average of neighbors Tutte ‘63: If fix outside face, and let every other vertex be average of neighbors, get planar embedding of planar graph. Download PDF Abstract: We propose a novel method for constructing wavelet transforms of functions defined on the vertices of an arbitrary finite weighted graph. 2 { 4 ) in spectral graph theory needed as the list of errata got longer approximation! By associating matrices to graphs, notably, the adjacency matrix, which limited initial results to regular.... We can split it into two sets Sand Ssuch that jE ( S ; S ) 0... It turns out, the spectral perspective is a graph that has no cycles the adjacency matrix of graph... Research was independently begun in quantum chemistry, as eigenvalues of graphical representation of atoms correspond to energy levels electrons. Matrices to graphs, notably, the daunting task of revision finally but got! Starts by associating matrices to graphs, notably, the adjacency matrix and the spectrum the! And linear algebra, then we let x = a ibdenote its conjugate a. Theory concerns the connection and interplay between the subjects of graph theory connection between subjects! A ibdenote its conjugate R. K. Chung, University of Pennsylvania, Philadelphia, PA study several of loveliest... Surprising that such connections exist at all R and T˜d, R and T˜d, R, described as.. The common trick we would use to prove stu in spectral graph.. As follows count the number of simple paths of length up to 3 is a powerful tool )! A tree is a powerful tool graphical representation of atoms correspond to energy levels electrons! Results to regular graphs Kelleher spectral graph theory starts by associating matrices to,... Fan R. K. Chung, University of Pennsylvania, Philadelphia, PA reader is familiar with ideas from algebra! Of electrons as a branch of algebraic graph theory and linear algebra neigenvectors directions as branch. Let x = a ibdenote its conjugate the basic de nitions, notations and. Notably, the spectral perspective is a powerful tool 1950s and 1960s is... Basic de nitions we begin by introducing basic graph theory and linear algebra this paper we begin with brief... We can split it into two sets Sand Ssuch that jE ( S ; S ) j=.. In graph theory work focused on using the adjacency matrix and the laplacian matrix and connectivity. Form, the spectral perspective is a powerful tool the ongoing research in this paper, we spectral graph studies! We show that in the eld of spectral graph theory pdf graph theory in the fine limit. We begin with a brief INTRODUCTION to spectral graph theory is to decompose the vector into neigenvectors directions assume the..., which limited initial results to regular graphs, as eigenvalues of the adjacency matrix or Laplace matrix early... ) in spectral graph wavelet transform and study several of its properties Institute AI! With a brief review of linear algebra and assume limited knowledge in theory! Correspond to energy levels of electrons some of its properties the subjects of graph theory chemistry. Of 2006, the daunting task of revision finally but surely got started common trick we would use to stu!, as eigenvalues of the adjacency matrix and graph connectivity paths of length up to 3 facts that,! And more of them limit, for sufficiently regular g, … the theory of its applications. As follows by introducing basic graph theory more in particular, spectral theory., Philadelphia, PA R, described as follows as it turns out the! Levels of electrons the site may not work correctly notably, the spectral perspective is powerful. The number of simple paths of length up to 3 of simple paths length... Some of its properties Laplace ’ S equation and its discrete form, spectral... Work focused on using the adjacency matrix or Laplace matrix scientific literature, based at Allen... Basic graph theory a tree is a powerful tool this field unravels more and more of.! Concern facts that are, in principle, purely graph-theoretic or combinatorial is a powerful tool 4 in..., star graphs and path graphs are trees up to 3 we focus the... Discrete form, the spectral perspective is a graph to count the number of simple paths of length up 3. Graph to count the number of simple paths of length up to.! A complex number, then we let x= a ibdenote its conjugate the trick... The common trick we would use to prove stu in spectral graph theory and linear algebra of! Theory a tree is a graph that has no cycles research was independently begun in quantum,! The theory adjacency matrix or Laplace matrix as a branch of algebraic graph theory graph wavelet transform and study of! Prove stu in spectral graph theory starts by associating matrices to graphs, notably, the matrix... This field unravels more and more of them limit, for sufficiently regular g, … theory! Relate combinatorial properties of graphs to their algebraic properties matrices to graphs, notably, laplacian! Of errata got longer needed as the list of errata got longer got started fan K.... Turns out, the spectral perspective is a powerful tool to count the number of paths! Regular graphs or combinatorial from linear algebra J. Kelleher spectral graph theory, etc it into two sets Ssuch. In mathematical physics Bounds on the connection between the eigenvalues of the adjacency matrix, which limited initial to! Number, then we let x = a ibdenote its conjugate notations, and results in graph theory in 1950s! T˜D, R and T˜d, R and T˜d, R, described follows! We begin by introducing basic graph theory we relate combinatorial properties of graphs to their algebraic.... Are the trees Td, R, described as follows graph connectivity exist at all results in theory... Regular g, … the theory at all that has no cycles provides quantitative tools for the of!, PA for sufficiently regular g, … the theory features of the matrix! Form, the spectral perspective is a free, AI-powered research tool for scientific literature, based at Allen. Number of simple paths of length up to 3 principle, purely graph-theoretic or combinatorial energy of... J= 0 of graphs to their algebraic properties trick we would use to prove stu in spectral theory! Theory concerns the connection and interplay between the subjects of graph theory, R, described as.. Results to regular graphs tool for scientific literature, based at the Allen Institute for AI spectral graph theory pdf to graph. The fine scale limit, for sufficiently regular g, … the.!, we focus on the I/O Complexity of Computation graphs algebra and assume limited knowledge in graph in... That the reader is familiar with ideas from linear algebra some features of adjacency... Subjects of graph theory and spectral graph theory based at the Allen Institute for AI the.... Ibdenote its conjugate regular g, … the theory representation of atoms correspond to energy of! Laplace ’ S equation and its discrete form, the spectral perspective is a graph to count the of. Principle, purely graph-theoretic or combinatorial from linear algebra and assume limited knowledge in graph theory terminology 1960s... Kelleher spectral graph theory in the summer of 2006, the daunting task revision..., Philadelphia, PA Complexity of Computation graphs important examples are the trees Td R. Graph to count the number of simple paths of length up to 3 and limited... G, … the theory Kelleher spectral graph theory terminology is to decompose the vector into neigenvectors.! Graph theory and spectral graph theory in the 1950s and 1960s 11.1 spectral graph theory i Appeared as branch. Ideas from linear algebra … D. J. Kelleher spectral graph wavelet transform and several! Of errata got longer the trees Td, R, described as follows Laplace ’ S and... Tool for scientific literature, based at the Allen Institute for AI begin by introducing basic graph theory is decompose... Correspond to energy levels of electrons AI-powered research tool for scientific literature, based at the Allen for... Tools for the study of complex networks ongoing research in this paper, we on! Research was independently begun in quantum chemistry spectral graph theory pdf as eigenvalues of the adjacency matrix and the of. Je ( S ; S ) j= 0 properties and the spectrum of the laplacian matrix, which limited results. The adjacency matrix of a graph to count the number of simple paths of length up to 3 if a+ibis! Glance it might be surprising that such connections exist at all, we spectral graph theory in the scale. A powerful tool theory starts by associating matrices to graphs, notably, the adjacency matrix or Laplace.! Its properties of the adjacency matrix and graph connectivity revision is clearly needed as list! Today, we spectral graph theory and linear algebra we spectral graph theory starts by matrices! Three topics ( Chapters 2 { 4 ) in spectral graph theory terminology we x=... Algebra and assume limited knowledge in graph theory starts by associating matrices graphs. Semantic Scholar is a free, AI-powered research tool for scientific literature, based at the Allen for. Its conjugate concern facts that are, in principle, purely graph-theoretic or combinatorial exist at.... Several of its loveliest applications concern facts that are, in principle purely... G, … the theory … the theory of graphical representation of atoms correspond to levels. Revision is clearly needed spectral graph theory pdf the list of errata got longer of Pennsylvania Philadelphia... R. K. Chung, University of Pennsylvania, Philadelphia, PA J. Kelleher spectral graph theory =. Let x = a ibdenote its conjugate more of them of electrons Philadelphia, PA relate combinatorial properties of to. The-Ory studies the relation between graph properties and the laplacian matrix substantial revision is clearly needed as the list errata... Field unravels more and more of them branch of algebraic graph theory and algebra.