Diameter of General Knödel Graphs

Abstract: The Kn"odel graph

W_{D e l t a, n}

is a

D e l t a

-regular bipartition graph on

n g e 2^{D e l t a}

vertices and

n

is an even integer. The vertices of

W_{D e l t a, n}

are the pairs

(i, j)

with

i = 1, 2

and

0 l e j l e n / 2 - 1

. For every

j

,

0 l e j l e n / 2 - 1

, there is an edge between vertex

(1, j)

and every vertex

(2, (j + 2^{k} - 1) m o d (n / 2))

, for

k = 0, 1, c d o t s, D e l t a - 1

. In this paper we obtain some formulas for evaluating the distance of vertices of the Kn"odel graph and by them, we provide the formula

d i a m (W_{D e l t a, n}) = 1 + l c e i l f r a c n - 2 2^{D e l t a} - 2 c e i l

for the diameter of

W_{D e l t a, n}

, where

n g e (2 D e l t a - 5) (2^{D e l t a} - 2) + 4

.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: Diameter of General Knödel Graphs