COSPECTRALITY MEASURES OF GRAPHS WITH AT MOST SIX VERTICES

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 spectralambda_۱ geq lambda_۲ geq cdots geq lambda_n ;;;text{and};;; lambda'_۱ geq lambda'_۲ geq cdots geq lambda'_n, respectively. Define the distance between the spectra of G_n and G'_n aslambda(G_n,G'_n) =sum_{i=۱}^n (lambda_i-lambda'_i)^۲ ;;; big(text{or use}; sum_{i=۱}^n|lambda_i-lambda'_i|big).Define the cospectrality of G_n bytext{cs}(G_n) = min{lambda(G_n,G'_n) ;:; G'_n ;;text{not isomorphic to} ; G_n}.Let text{cs}_n = max{text{cs}(G_n) ;:; G_n ;;text{a graph on}; n ;text{vertices}}.Investigation of text{cs}(G_n) for special classes of graphs and finding a good upper bound on text{cs}_n are two main questions in thissubject.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.

کلیدواژه ها:

Spectra of graphs ، edge deletion ، adjacency matrix of a graph