×

Recognizing bipartite incident-graphs of circulant digraphs. (English) Zbl 0941.05059

Widmayer, Peter (ed.) et al., Graph theoretic concepts in computer science. 25th international workshop, WG ’99, Ascona, Switzerland, June 17-19, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1665, 215-227 (1999).
Summary: Knödel graphs and Fibonacci graphs are two classes of bipartite incident-graphs 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(n\log^5 n)\)-time algorithm to recognize Knödel 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 Knödel graphs are edge-transitive, apart those of \(2^k- 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.
For the entire collection see [Zbl 0929.00074].

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite