COSPECTRALITY MEASURES OF GRAPHS WITH AT MOST SIX VERTICES

Abdollahi, A.; Janbaz, Sh.; Oboudi, M.R.

COSPECTRALITY MEASURES OF GRAPHS WITH AT MOST SIX VERTICES

Document Type : Research Paper

Authors

¹ University of Isfahan

² Shiraz University

Abstract

Cospectrality of two graphs measures the differences between the ordered spectrum of these graphs in various ways. Actually, the origin of this concept came back to Richard Brualdi's problems that are proposed in cite{braldi}: Let

G_{n}

and

G_{n}^{'}

be two nonisomorphic simple graphs on

n

vertices with spectra

l a m b d a_{1} g e q l a m b d a_{2} g e q c d o t s g e q l a m b d a_{n};;; t e x t a n d;;; l a m b d a_{1}^{'} g e q l a m b d a_{2}^{'} g e q c d o t s g e q l a m b d a_{n}^{'},

respectively. Define the distance between the spectra of

G_{n}

and

G_{n}^{'}

l a m b d a (G_{n}, G_{n}^{'}) = s u m_{i = 1}^{n} (l a m b d a_{i} - l a m b d a_{i}^{'})^{2};;; b i g (t e x t o r u s e; s u m_{i = 1}^{n} | l a m b d a_{i} - l a m b d a_{i}^{'} | b i g) .

Define the cospectrality of

G_{n}

t e x t c s (G_{n}) = m i n l a m b d a (G_{n}, G_{n}^{'}); :; G_{n}^{'};; t e x t n o t i s o m o r p h i c t o; G_{n} .

Let

t e x t {c s}_{n} = m a x t e x t c s (G_{n}); :; G_{n};; t e x t a g r a p h o n; n; t e x t v e r t i c e s .

Investigation of

t e x t c s (G_{n})

for special classes of graphs and finding a good upper bound on

t e x t {c s}_{n}

are two main questions in this
subject.
In this paper, we briefly give some important results in this direction and then we collect all cospectrality measures of graphs with at most six vertices with respect to three norms. Also, we give the shape of all graphs that are closest (with respect to cospectrality measure) to a given graph

G

Keywords

References

[1] D. Stevanivi´c, Research problems from the Aveiro workshop on graph spectra, Linear Algebra and its Applications, 423 (2007) 172-181.
[2] A. Abdollahi and M. R. Oboudi, Cospectrality of graphs, Linear Algebra and its Applications, 451 (2014) 169-181.
[3] A. Abdollahi, Sh. Janbaz and M. R. Oboudi, Distance between spectra of graphs, Linear Algebra and its Applications, 466 (2015) 401-408.
[4] T. Tao, Topics in Random Matrix Theory, Graduate Studies in Mathematics, American Mathematical Society, Volume 132, 2012.