Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Non-isomorphic graphs with cospectral symmetric powers. | Non-isomorphic graphs with cospectral symmetric powers Amir Rahnamai Barghi Department of Mathematics Faculty of Science . Toosi University of Technology . Box 16315-1618 Tehran Iran rahnama@ Ilya Ponomarenko Petersburg Department of . Steklov Institute of Mathematics Fontanka 27 St. Petersburg 191023 Russia inp@. ru Submitted Nov 22 2008 Accepted Sep 14 2009 Published Sep 25 2009 Mathematics Subject Classification 05C50 05C60 05E30 Abstract The symmetric m-th power of a graph is the graph whose vertices are m-subsets of vertices and in which two m-subsets are adjacent if and only if their symmetric difference is an edge of the original graph. It was conjectured that there exists a fixed m such that any two graphs are isomorphic if and only if their m-th symmetric powers are cospectral. In this paper we show that given a positive integer m there exist infinitely many pairs of non-isomorphic graphs with cospectral m-th symmetric powers. Our construction is based on theory of multidimensional extensions of coherent configurations. 1 Introduction Let G be a graph with vertex set Given a positive integer m the symmetric m-th power of G is the graph G m whose vertices are m-subsets of V and in which two m-subsets are adjacent if and only if their symmetric difference is an edge in G 11 . One of the motivations for studying symmetric powers comes from the graph isomorphism problem which is to recognize in an efficient way whether two given graphs are isomorphic. To be more precise we cite a paragraph from paper 2 The author was partially supported by RFBR grants 07-01-00485 08-01-00379 and 08-01-00640. 1 All graphs in this paper are undirected without loops and multiple edges. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R120 1 If it were true for some fixed m that any two graphs G and H are isomorphic if and only if their m-th symmetric powers are cospectral then we would have a polynomial-time algorithm for solving the graph .
