Knödel Graph

The Knödel graph W_(Delta,n) is a regular bipartite graph of vertex degree Delta on n nodes for even n>=2 and 1<=Delta<=|_log_2n_| with edges defined as follows. Label the vertices (i,j) with i=1,2 and 0<=j<=n/2-1. Then there is an edge between (1,j) and (2,k) for every k=j+2^p-1 (mod n/2) where p=0, ..., Delta-1 (Fertin and Raspaud 2004, Clancy et al. 2019).

This class of graphs was introduced by Knödel (1975) in constructing a time-optimal algorithm for gossiping among n vertices with even n, but were only formally defined by Fraigniaud and Peters (2001) (Fertin and Raspaud 2004).

Knödel graphs are Cayley and vertex-transitive graphs (Fertin and Raspaud 2004). They are also Haar graphs.

Special cases are summarized in the following table.

The edge connectivity of W_(Delta,n) is given by


and the vertex connectivity satisfies


(Fertin and Raspaud 2004).

Zheng et al. (2008) showed that the graph crossing numbers of the cubic Knödel graph W_(3,n) is given by

cr(W_(3,n))=|_n/6_|+(n (mod 6))/2

for even n>=12 (Clancy et al. 2019).

See also

Cycle Graph, Haar Graph, Honeycomb Toroidal Graph, I Graph, Ladder Rung Graph

Explore with Wolfram|Alpha


Clancy, K.; Haythorpe, M.; and Newcombe, A. "Knödel Graph." §2.6 in "A Survey of Graphs with Known or Bounded Crossing Numbers." 15 Feb 2019., G. and Raspaud, A. "A Survey on Knödel Graphs." Disc. Appl. Math. 137, 173-195, 2004.Fraigniaud, P. and Peters, J. G. "Minimum Linear Gossip Graphs and Maximal Linear (Delta;k)-Gossip Graphs." Networks 38, 150-162, 2001.Knödel, W. "New Gossips and Telephones." Disc. Math. 13, 95, 1975.Zheng, W.; Lin, X.; Yang, Y.; and Deng, C. "The Crossing Number of Knödel Graph W_(3,n)." Util. Math. 75, 211-224, 2008.

Cite this as:

Weisstein, Eric W. "Knödel Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications