Recognizing Bipartite Incident-Graphs of Circulant Digraphs

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,\dots,\gamma_k$, $0\leq \gamma_i \leq n-1$, $i=0,\dots,k$, the {\em 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 $x_1\in V_1$, and any $x_2\in V_2$, $\{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}$. \KGs\ and \FGs\ 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 \KGs, and that the same technique applies to \FGs. 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 \KGs\ 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.
Type de document :
Communication dans un congrès
P. Widmayer, G. Neyer, S. Eidenbenz. International Workshop on Graph Theoretic Concepts in Computer Science - WG'99, 1999, Ascona, Switzerland, Springer, 1665, pp.215-227, 1999, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00098892
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:39:57
Dernière modification le : jeudi 11 janvier 2018 - 06:20:00

Identifiants

  • HAL Id : inria-00098892, version 1

Collections

Citation

Johanne Cohen, Pierre Fraigniaud, Cyril Gavoille. Recognizing Bipartite Incident-Graphs of Circulant Digraphs. P. Widmayer, G. Neyer, S. Eidenbenz. International Workshop on Graph Theoretic Concepts in Computer Science - WG'99, 1999, Ascona, Switzerland, Springer, 1665, pp.215-227, 1999, Lecture Notes in Computer Science. 〈inria-00098892〉

Partager

Métriques

Consultations de la notice

134