The shortest path problem in the Knödel graph

The Knödel graph WΔ,nWΔ,n is a graph of even order n and degree Δ   where 2≤Δ≤⌊log2⁡n⌋2≤Δ≤⌊log2⁡n⌋. Most properties of the Knödel graph are known only for WΔ,2ΔWΔ,2Δ and WΔ−1,2Δ−2WΔ−1,2Δ−2. In this paper we study the shortest path problem in WΔ,nWΔ,n for all Δ and n  . We give a tight bound on the distance between any two vertices in WΔ,nWΔ,n. We show that for almost all Δ  , the presented bound differs from actual distance by at most 2. The proofs are constructive and allow us to present an O(log⁡n)O(log⁡n) time algorithm to construct a short path between any pair of vertices in WΔ,nWΔ,n. The diameter of WΔ,nWΔ,n is known only for n=2Δn=2Δ. Using our results on the shortest path problem, we present tight upper and lower bounds on the diameter of the Knödel graph for all Δ and n.