2017/02/07 by S. Morteza Mirafzal, Mirafzal, S. Morteza
Engineering · Mathematics · #05C25 #05C69 #94C15 #FOS: Mathematics #Finite Group Theory Research #Group Theory (math.GR) #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1702.02095
openalex publication_date 2017/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Kneser graph K(n, k) has as vertices all k-element subsets of [n]=\1,2,...,n \ and an edge between any two vertices that are disjoint. If n=2k+1, then K(n, k) is called an odd graph. Let n >4 and 1< k < (n)/(2) . In the present paper, we show that if the Kneser graph K(n,k) is of even order where n is an odd integer or both of the integers n,k are even, then K(n,k) is a vertex-transitive non Cayley graph. Although, these are special cases of Godsil [8], unlike his proof that uses some very deep group-theoretical facts, ours uses no heavy group-theoretic facts. We obtain our results by using some rather elementary facts of number theory and group theory. We show that "almost all" odd graphs are of even order, and consequently are vertex-transitive non Cayley graphs. Finally, we show that if k > 4 is an even integer such that k is not of the form k = 2t for some t> 2 , then the line graph of the odd graph Ok+1 is a vertex-transitive non Cayley graph.