Integral Graph
المؤلف:
Harary, F. and Schwenk, A. J
المصدر:
"Which Graphs have Integral Spectra?" In Graphs and Combinatorics (Ed. R. Bari and F. Harary). Berlin: Springer-Verlag
الجزء والصفحة:
...
26-4-2022
2424
Integral Graph
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 
, 2, ... nodes are 0, 2, 3, 6, 10, 20, 33, 71, ... (OEIS A077027), illustrated above for small 
.
The numbers of connected simple integral graphs on 
, 2, ... nodes are 1, 1, 1, 2, 3, 6, 7, 22, 24, 83, ... (OEIS A064731), illustrated above for small 
.
The following table lists common graph classes and the their members which are integral.
| graph |
integral for  of the form |
| antiprism graph |
3 |
complete graph  |
all |
cycle graph  |
2, 3, 4, 6 |
| empty graph |
all |
| prism graph |
3, 4, 6 |
star graph  |
 |
wheel graph  |
4 |
The following table lists some special named graphs that are integral and gives their spectra.
| graph |
graph spectrum |
| 16-cell |
 |
| 24-cell |
 |
| Clebsch graph |
 |
| cubical graph |
 |
| cuboctahedral graph |
 |
| Desargues graph |
 |
| Hall-Janko graph |
 |
| Hoffman graph |
 |
| Hoffman-Singleton graph |
 |
| Levi graph |
 |
| M22 graph |
 |
| McLaughlin graph |
 |
| octahedral graph |
 |
| pentatope |
 |
| Petersen graph |
 |
| Shrikhande graph |
 |
 -simplex |
 |
| small triakis octahedral graph |
 |
| Sylvester graph |
 |
| tesseract |
 |
| tetrahedral graph |
 |
| truncated tetrahedral graph |
 |
| utility graph |
 |
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."
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
