Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: a matrix representation of graphs and its spectrum as a graph invariant. | A MATRIX REPRESENTATION OF GRAPHS AND ITS SPECTRUM AS A GRAPH INVARIANT David Emms Department of Computer Science University of York York YO10 5DD . demms@ Edwin R. Hancock Department of Computer Science University of York York YO10 5DD . erh@ Simone Severini Department of Mathematics and Department of Computer Science University of York York YO10 5DD . ss54@ Richard C. Wilson Department of Computer Science University of York York YO10 5DD . Submitted Nov 16 2005 Accepted Mar 16 2006 Published Apr 4 2006 2000 Mathematics Subject Classification 05E30 05C60 Abstract We use the line digraph construction to associate an orthogonal matrix with each graph. From this orthogonal matrix we derive two further matrices. The spectrum of each of these three matrices is considered as a graph invariant. For the first two cases we compute the spectrum explicitly and show that it is determined by the spectrum of the adjacency matrix of the original graph. We then show by computation that the isomorphism classes of many known families of strongly regular graphs up to 64 vertices are characterized by the spectrum of this matrix. We conjecture that this is always the case for strongly regular graphs and we show that the conjecture is not valid for general graphs. We verify that the smallest regular graphs which are not distinguished with our method are on 14 vertices. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R34 1 1 Introduction Graphs are often conveniently represented using matrices for example the adjacency matrix the Laplacian matrix etc. 5 . Many important properties of a graph are encoded in the eigenvalues of the matrix representation. However eigenvalues generally fail to separate isomorphism classes. In this paper we consider some matrix representations inspired by the notion of coined quantum walks 1 . Since strongly regular graphs give rise to relatively large sets of non-isomorphic graphs .
