HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# Recognizing Knödel graphs

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.
Keywords :
Document type :
Journal articles
Domain :

https://hal.inria.fr/inria-00100969
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

### Identifiers

• HAL Id : inria-00100969, version 1

### Citation

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

Record views