Abstract

A graph $G$ is said to be an integral graph if all the eigenvalues of the adjacency matrix of $G$ are integers. A natural question to ask is which graphs are integral. In general, characterizing integral graphs seems to be a difficult task. In this paper, we define some graph operations on ordered triple of graphs. We compute their spectrum and, as an application, we give some new methods to construct infinite families of integral graphs starting with either an arbitrary integral graph or integral regular graph. Also, we present some new infinite families of integral graphs by applying our graph operations to some standard graphs like complete graphs, complete bipartite graphs etc.

Keywords: Integral graphs; Kronecker product.

MSC: 05C50

Pages:  53--64     

Volume  69 ,  Issue  1 ,  2017