Integral graph
Encyclopedia
In the mathematical
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, an integral graph is a graph whose spectrum
Spectral graph theory
In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix or Laplacian matrix....

 consists entirely of integers. In other words, a graphs is an integral graph if all the eigenvalues of its characteristic polynomial
Characteristic polynomial
In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....

 are integers.

The notion was introduced in 1974 by Harary and Schwenk.

Examples

  • The complete graph
    Complete graph
    In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...

     Kn is integral for all n.
  • The edgeless graph  is integral for all n.
  • Among the cubics symmetric graphs the utility graph, the Petersen graph
    Petersen graph
    In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...

    , the Nauru graph
    Nauru graph
    In the mathematical field of graph theory, the Nauru graph is a symmetric bipartite cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru....

     and the Desargues graph
    Desargues graph
    In the mathematical field of graph theory, the Desargues graph is a distance-transitive cubic graph with 20 vertices and 30 edges. It is named after Gérard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial...

     are integral.
  • The Higman–Sims graph, the Hall–Janko graph, the Clebsch graph
    Clebsch graph
    In the mathematical field of graph theory, the Clebsch graph is an undirected graph with 16 vertices and 40 edges. It is named after Alfred Clebsch, a German mathematician who discovered it in 1868...

    , the Hoffman–Singleton graph, the Shrikhande graph
    Shrikhande graph
    In the mathematical field of graph theory, the Shrikhande graph is a named graph discovered by S. S. Shrikhande in 1959. It is a strongly regular graph with 16 vertices and 48 edges, with each vertex having a degree of 6.-Properties:...

     and the Hoffman graph
    Hoffman graph
    In the mathematical field of graph theory, the Hoffman graph is a 4-regular graph with 16 vertices and 32 edges discovered by Alan Hoffman. Published in 1963, it is cospectral to the hypercube graph Q4....

    are integral.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK