Integral Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

IntegralGraphs

An integral graph, not to be confused with an integral embedding of a graph, is defined as a graph whose graph spectrum consists entirely of integers. The notion was first introduced by Harary and Schwenk (1974). The numbers of simple integral graphs on n=1, 2, ... nodes are 0, 2, 3, 6, 10, 20, 33, 71, ... (OEIS A077027), illustrated above for small n.

IntegralConnectedGraphs

The numbers of connected simple integral graphs on n=1, 2, ... nodes are 1, 1, 1, 2, 3, 6, 7, 22, 24, 83, ... (OEIS A064731), illustrated above for small n.

The following table lists common graph classes and the their members which are integral.

graph integral for n of the form

antiprism graph 3

complete graph K_n all

cycle graph C_n 2, 3, 4, 6

empty graph all

prism graph 3, 4, 6

star graph S_n n^2+1

wheel graph W_n 4

The following table lists some special named graphs that are integral and gives their spectra.

graph graph spectrum

16-cell (-2)^30^46^1

24-cell (-4)^2(-2)^80^94^48^1

Clebsch graph (-3)^51^(10)5^1

cubical graph (-3)^1(-1)^31^33^1

cuboctahedral graph (-2)^50^32^34^1

Desargues graph (-3)^1(-2)^4(-1)^51^52^43^1

Hall-Janko graph (-4)^(63)6^(36)36^1

Hoffman graph (-4)^1(-2)^40^62^44^1

Hoffman-Singleton graph (-3)^(21)2^(28)7^1

Tutte 8-cage (-3)^1(-2)^90^(10)2^93^1

M22 graph (-6)^(21)2^(55)16^1

McLaughlin graph (-28)^(22)2^(252)112^1

octahedral graph (-2)^20^34^1

pentatope (-1)^44^1

Petersen graph (-2)^41^53^1

Shrikhande graph (-2)^92^66^1

n-simplex (-1)^nn^1

small triakis octahedral graph (-2)^60^42^36^1

Sylvester graph (-3)^9(-1)^(10)5^12^(16)

tesseract (-4)^1(-2)^40^62^44^1

tetrahedral graph (-1)^33^1

truncated tetrahedral graph (-2)^3(-1)^30^22^33^1

utility graph (-3)^10^43^1

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Harary, F. and Schwenk, A. J. "Which Graphs have Integral Spectra?" In Graphs and Combinatorics (Ed. R. Bari and F. Harary). Berlin: Springer-Verlag, pp. 45-51, 1974.Sloane, N. J. A. Sequences 064731 A and A077027 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Integral Graph

Cite this as:

Weisstein, Eric W. "Integral Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/IntegralGraph.html

Integral Graph

See also

Explore with Wolfram|Alpha

References

Referenced on Wolfram|Alpha

Cite this as:

Subject classifications