Seyed Reza Musawi ; Esameil Nazari Kiashi - Diameter of General Knödel Graphs

fi:12318 - Fundamenta Informaticae, October 14, 2023, Volume 190, Issue 1
Diameter of General Knödel GraphsArticle

Authors: Seyed Reza Musawi ; Esameil Nazari Kiashi

    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) \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$.

    Volume: Volume 190, Issue 1
    Published on: October 14, 2023
    Accepted on: September 23, 2023
    Submitted on: September 23, 2023
    Keywords: Mathematics - Combinatorics,05C12, 05C30, 05C38

    Consultation statistics

    This page has been seen 562 times.
    This article's PDF has been downloaded 214 times.