Families of graphs having few distinct distance eigenvalues with arbitrary diameter

Publications

Families of graphs having few distinct distance eigenvalues with arbitrary diameter

Author : Dr Fouzul Atik

Year : 2015

Publisher : International Linear Algebra Society

Source Title : Electronic Journal of Linear Algebra

Document Type :

Abstract

The distance matrix of a simple connected graph G is D(G) = (dij), where dij is the distance between ith and jth vertices of G. The multiset of all eigenvalues of D(G) is known as the distance spectrum of G. Lin et al.(On the distance spectrum of graphs. Linear Algebra Appl., 439:1662-1669, 2013) asked for existence of graphs other than strongly regular graphs and some complete k-partite graphs having exactly three distinct distance eigenvalues. In this paper some classes of graphs with arbitrary diameter and satisfying this property is constructed. For each k ∈ {4, 5,⋯, 11} families of graphs that contain graphs of each diameter grater than k – 1 is constructed with the property that the distance matrix of each graph in the families has exactly k distinct eigenvalues. While making these constructions we have found the full distance spectrum of square of even cycles, square of hypercubes, corona of a transmission regular graph with K2, and strong product of an arbitrary graph with Kn.