Samiksha Jaiswal (Editor)

Integral graph

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In the mathematical field of graph theory, an integral graph is a graph whose spectrum consists entirely of integers. In other words, a graph is an integral graph if all of the roots of its characteristic polynomial are integers.

The notion was introduced in 1974 by Harary and Schwenk.

Examples

  • The complete graph Kn is integral for all n.
  • The edgeless graph K ¯ n is integral for all n.
  • Among the cubic symmetric graphs the utility graph, the Petersen graph, the Nauru graph and the Desargues graph are integral.
  • The Higman–Sims graph, the Hall–Janko graph, the Clebsch graph, the Hoffman–Singleton graph, the Shrikhande graph and the Hoffman graph are integral.

    • References

    Integral graph Wikipedia
    (Text) CC BY-SA