Some properties of the knödel graph w (K, 2^k), k ≥ 4

Knödel graphs have, of late, come to be used as strong competitors for hypercubes in the realms of broadcasting and gossiping in interconnection networks. For an even positive integer n and 1 ≤ Δ ≤ ⌊log₂ n⌋, the general Knödel graph W_Δ,n is the Δ-regular bipartite graph with bipar-tition sets X = {x₀, x₁, …, xⁿ ₋₁} and Y = {y₀, y₁, …, yⁿ ₋₁} such that x_j is adjacent n . The edge x to y_j, y_j+2 ¹ ₋₁,²y_j+2 ² ₋₁, …, y_{j+2Δ−1−1}, with² suffixes being taken modulo_2j y_{j+2i −1} at x_j and the edge y_j x_{j−(2i −1)} at y_j are called edges of dimension i at the stars centered at x_j and y_j respectively. In this paper, we concentrate on the Knödel graph W_k = W_k,2k with k ≥ 4. We show that for k ≥ 4, any automorphism of W_k fixes the set of 0-dimensional edges of W_k . We determine the automorphism group Aut(W_k) of W_k and show that it is isomorphic to the dihedral group D_2k−1. In addition, we determine the spectrum of W_k and prove that it is never integral. As a by-product of our results, we obtain three new proofs showing that, for k ≥ 4, W_k is not isomorphic to the hyper-cube H_k of dimension k, and a new proof for the result that W_k is not edge-transitive.