GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Algebra
  • Applied Mathematics
  • Calculus and Analysis
  • Discrete Mathematics
  • Foundations of Mathematics
  • Geometry
  • History and Terminology
  • Number Theory
  • Probability and Statistics
  • Recreational Mathematics
  • Topology
  • Alphabetical Index
  • Random Entry
  • New in MathWorld

This view

  • Original page
  • New address

GeezerVison is showing mathworld.wolfram.com — Integral Graph -- from Wolfram MathWorld

Search

Integral Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
IntegralGraphs

An integral graph, not to be confused with an integral drawing of a graph, is 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 1, 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.

Braga et al. (2026a) proved that every simple graph having a pendant path with at least three edges has a graph eigenvalue in (1,2cos(pi/9)] and another in [-2cos(pi/9),-1). Consequently, every such graph is nonintegral. The positive interval is best possible for real symmetric matrices with such a terminal path. Sharpness for adjacency matrices of simple graphs is not asserted (Braga et al. 2026a).

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

graphintegral for n of the form
antiprism graph3
complete graph K_nall
cycle graph C_n2, 3, 4, 6
empty graphall
prism graph3, 4, 6
star graph S_nn^2+1
wheel graph W_n4

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

graphgraph spectrum
16-cell graph K_(4×2)(-2)^30^46^1
24-cell graph(-4)^2(-2)^80^94^48^1
Clebsch graph(-3)^51^(10)5^1
cubical graph Q_3(-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 K_(2,2,2)(-2)^20^34^1
pentatope graph K_5(-1)^44^1
Petersen graph P(-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 graph Q_4(-4)^1(-2)^40^62^44^1
tetrahedral graph K_4(-1)^33^1
truncated tetrahedral graph(-2)^3(-1)^30^22^33^1
utility graph K_(3,3)(-3)^10^43^1

Among connected unicyclic graphs, the triangle graph C_3 is the only nonbipartite integral graph (Braga et al. 2026b).

See also

Eigenvalue, Graph Spectrum, Unicyclic Graph, Unit-Distance Graph

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

  • integral graph
  • .333...
  • German numeral names

References

Braga, R. O.; Moraes, J. C.; and Santos, M. C. "Pendant Paths and Integral Generalized Sun Graphs." 23 Sep 2026a. https://arxiv.org/abs/2609.28754.Braga, R. O.; Moraes, J. C.; and Santos, M. C. "Spectral Asymmetry and Odd Cycles in Integral Graphs." 16 Oct 2026b. https://arxiv.org/abs/2610.22773.Harary, F. and Schwenk, A. J. "Which Graphs Have Integral Spectra?" In Graphs and Combinatorics (Ed. R. Bari and F. Harary). Berlin, Germany: Springer-Verlag, pp. 45-51, 1974.Sloane, N. J. A. Sequences A064731 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

Subject classifications

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.