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
for even 
(Clancy et al. 2019).
See also
Cycle Graph, Haar Graph, Honeycomb Toroidal Graph, I Graph, Ladder Rung Graph
Explore with Wolfram|Alpha
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.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Knödel Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/KnoedelGraph.html