SPECTRAL CHARACTERIZATION OF ODD GRAPHS OK, K-LESS-THAN-OR-EQUAL-TO-6

Abstract

Let k be an integer with k greater-than-or-equal-to 2. The Odd graph O(k) has the (k - 1)-subsets of {1,2,...,2k - 1} as vertices, and two vertices are adjacent if and only if their corresponding subsets are disjoint. We prove that the odd graphs O(k) (k less-than-or-equal-to 6) are characterized by their spectra among connected regular graphs.