HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Recognizing Knödel graphs

Johanne Cohen 1 Pierre Fraigniaud Cyril Gavoille
1 RESEDAS - Software Tools for Telecommunications and Distributed Systems
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Given a circulant digraph H=(V,A) of order n and of generators \gamma_0,...,\gamma_k , 0\leq \gamma_i \leq n-1 , i=0,...,k, the bipartite incident-graph of H is a bipartite graph G=(V_1,V_2,E) of order 2n where V_1=V_2=V, and, for any , and any , \{x_1,x_2\}\in E \Leftrightarrow (x_1,x_2)\in A \Leftrightarrow \exists i \in \{0,\dots,k\} \mid x_2 = x_1 + \gamma_i \pmod{n} . Knödel graphs and Fibonacci graphs are two types of such graphs. They correspond to \gamma_i=2^i-1, and \gamma_i=F(i+1)-1 , respectively. 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 a polynomial-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 know whether a polynomial-time algorithm exists for any infinite family of bipartite incident-graphs of circulant digraphs indexed by their number of vertices.
Document type :
Journal articles
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 2:53:13 PM
Last modification on : Friday, February 4, 2022 - 3:31:53 AM


  • HAL Id : inria-00100969, version 1



Johanne Cohen, Pierre Fraigniaud, Cyril Gavoille. Recognizing Knödel graphs. Discrete Mathematics, Elsevier, 2002, pp.41-62. ⟨inria-00100969⟩



Record views