Graph Spectrum

The set of graph eigenvalues of the adjacency matrix is called the spectrum of the graph. (But note that in physics, the eigenvalues of the Laplacian matrix of a graph are sometimes known as the graph's spectrum.) The spectrum of a graph  with -fold degenerate eigenvalues  is commonly denoted  (van Dam and Haemers 2003) or  (Biggs 1993, p. 8; Buekenhout and Parker 1998).

The product  over the elements of the spectrum of a graph  is known as the characteristic polynomial of , and is given by the characteristic polynomial of the adjacency matrix of  with respect to the variable .

The largest absolute value of a graph's spectrum is known as its spectral radius.

The spectrum of a graph may be computed in the Wolfram Language using Eigenvalues[AdjacencyMatrix[g]]. Precomputed spectra for many named graphs can be obtained using GraphData[graph, "Spectrum"].

A graph whose spectrum consists entirely of integers is known as an integral graph.

The maximum vertex degree of a connected graph  is an eigenvalue of  iff  is a regular graph.

Two nonisomorphic graphs can share the same spectrum. Such graphs are called cospectral. There seems to be no standard name for graphs known to be uniquely determined by their spectra. While they could conceivably be called spectrally unique, the term "determined by spectrum" has been used in practice (van Dam and Haemers 2003).

---

REFERENCES

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.

Buekenhout, F. and Parker, M. "The Number of Nets of the Regular Convex Polytopes in Dimension ." Disc. Math. 186, 69-94, 1998.

Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.Haemers, W. H. "Spectral Characterization of Graphs." In IPM Combinatorics II: Design Theory, Graph Theory, and Computational Methods. April 22-27, 2006, IPM, Tehran. http://www.ipm.ac.ir/combinatoricsII/abstracts/Haemers1.pdf.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 85, 1990.

van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.

Wilf, H. "Graphs and Their Spectra: Old and New Results." Congr. Numer. 50, 37-43, 1985.

اخر الاخبار

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

قسم صناعة الشبابيك يشرع بإدامة شباكين قديمين لمرقد الإمامين العسكريين (عليهما السلام)

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

موكب العتبتين المقدستين يحيي ذكرى استشهاد الإمام الهادي (عليه السلام) في سامراء

العتبة العسكرية المقدسة تكرّم وفد العتبة العباسية المقدسة لمشاركته في تقديم الخدمات للزائرين

المزيد

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

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

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

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

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