Diameter of General Knödel Graphs

Abstract

The Knödel graph $W_{\Delta ,n}$ is a $\Delta$-regular bipartition graph on $n\ge 2^{\Delta }$ vertices and $n$ is an even integer. The vertices of $W_{\Delta ,n}$ are the pairs $(i,j)$ with $i=1,2$ and $0\le j\le n/2-1$. For every $j$, $0\le j\le n/2-1$, there is an edge between vertex $(1,j)$ and every vertex $(2,(j+2^k-1)\mathrm{mod}(n/2))$, for $k=0,1,\cdots ,\Delta -1$. In this paper we obtain some formulas for evaluating the distance of vertices of the Knödel graph and by them, we provide the formula $diam(W_{\Delta ,n})=1+\lceil \frac{n-2}{2^{\Delta }-2}\rceil$ for the diameter of $W_{\Delta ,n}$, where $n\ge (2\Delta -5)(2^{\Delta }-2)+4$.

arXiv comment16 pages, 1 table, 2 figures