TITLE: Recognizing Knödel Graphs
AUTHORS: Johanne Cohen, Pierre Fraigniaud and Cyril Gavoille
ABSTRACT:
Knödel graphs form a class of bipartite incident-graph of circulant
digraphs. This class has been extensively studied for the purpose of
fast communications in networks, and it has deserved a lot of
attention in this context. In this paper, we show that there exists
an O(nlog5n)-time algorithm to recognize
Knödel graphs of order 2n. The algorithm is based on a
characterization of the cycles of length six in these graphs
(bipartite incident-graphs of circulant digraphs always have cycles of
length six). A consequence of our result is that the circulant
digraphs whose chords are the power of two minus one can be recognized
in O(nlog5n) time.