Integral graph
Encyclopedia
In the mathematical
field of graph theory
, an integral graph is a graph whose spectrum
consists entirely of integers. In other words, a graphs is an integral graph if all the eigenvalues of its characteristic polynomial
are integers.
The notion was introduced in 1974 by Harary and Schwenk.
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 graphComplete graphIn 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 graphPetersen graphIn 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 graphNauru graphIn 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 graphDesargues graphIn 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 graphClebsch graphIn 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 graphShrikhande graphIn 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 graphHoffman graphIn 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.