Several Properties Of Kneser Graph And Its Automorphism Group

LetΩbe a fixed set of size n.The Kneser graph J(n,k)has the vertex set V which is the k-subsets ofΩ,and the two subsets are adjacent if their intersection is empty(where,n,k are fixed positive integers with n＞2k,k＞1).These graphs are important because they enable us to translate many combinatorial problems about sets into graph theory.The researching about this family graphs could be found in many external papers but less in the internal.The most famous result is the Kneser conjecture which is from Lovāsz.L. C.D.Godsil and G.Royle has approached the properties of Kneser graphs from different angles and many results has been shown in their book[Ref.1].In this paper,we shall explore several properties of Kneser graph via the method related to algebraic and group theory,which should be introduced as follow.The first,we give a new proof which shown that the automorphism group of Kneser graph J(n,k)is isomorphic to the symmetric group Sym(n)by introducing a concept named fixing number.Second, we verify that the radius of Kneser graph J(n,k)equals to 2.By this, we should obtain simple corollary about Kneser graph is self-central. The last,with the aid of computer,we list the spectrums and Laplacian spectrums of some Kneser graphs with the special parameters,and a conjecture could be provided.