TOPICS

Knödel Graph

The Knödel graph is a regular bipartite graph of vertex degree on nodes for even and with edges defined as follows. Label the vertices with and . Then there is an edge between and for every where , ..., (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 vertices with even , 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 is given by

 (1)

and the vertex connectivity satisfies

 (2)

(Fertin and Raspaud 2004).

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

 (3) (4) (5)

for even (Clancy et al. 2019).

See also

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

Explore with Wolfram|Alpha

More things to try:

References

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. https://arxiv.org/pdf/1901.05155.pdf.Fertin, 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 -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 ." Util. Math. 75, 211-224, 2008.

Cite this as:

Weisstein, Eric W. "Knödel Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/KnoedelGraph.html