Tight Bound on the Diameter of the Knoedel Graph

摘要

The Knoedel graph W_(△,n) is a regular graph of even order and degree A where 2 ≤ △ ≤ [log_2 n]. Despite being a highly symmetric and widely studied graph, the diameter of W_(△,n) is known only for n = 2~△. In this paper we present a tight upper bound on the diameter of the Knodel graph for general case. We show that the presented bound differs from the diameter by at most 2 when △ ＜ α [log_2 n] for some 0 ＜ α ＜ 1 where α → 1 when n → ∞. The proof is constructive and provides a near optimal diametral path for the Knodel graph W_(△,n).