TITLE: Recognizing Bipartite Incident-Graphs of Circulant Digraphs
AUTHORS: Johanne Cohen, Pierre Fraigniaud and Cyril Gavoille
ABSTRACT:
Knodel graphs and Fibonacci graphs are two classes of bipartite
incident-graph of circulant digraphs. Both graphs have been
extensively studied for the purpose of fast communications in
networks, and they have deserved a lot of attention in this context.
In this paper, we show that there exists an
O(nlog5n)-time algorithm to recognize Knodel
graphs, and that the same technique applies to Fibonacci graphs. 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
none of the Knodel graphs are edge-transitive, apart those of
2k-2 vertices. An open problem that arises in this
field is to derive a polynomial-time algorithm for any infinite family
of bipartite incident-graphs of circulant digraphs indexed by their
number of vertices.