no. 3
On a problem of walks
Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 905-919.

En 1995, F. Jaeger et M.-C. Heydemann commencèrent à étudier une conjecture sur les opérations binaires apparentées aux homomorphismes de graphes de De Bruijn orientés. À cet effet, ils examinèrent la classe des graphes orientés G tels que pour tout entier k, G ait exactement n chemins de longueur k, où n est l’ordre de G. C. Delorme a apporté récemment quelques vues sur la conjecture d’origine. Le but de cet article est de décrire la conjecture et de faire le point sur les acquis.

In 1995, F. Jaeger and M.-C. Heydemann began to work on a conjecture on binary operations which are related to homomorphisms of De Bruijn digraphs. For this, they have considered the class of digraphs G such that for any integer k, G has exactly n walks of length k, where n is the order of G. Recently, C. Delorme has obtained some results on the original conjecture. The aim of this paper is to recall the conjecture and to report where all the authors arrived.

@article{AIF_1999__49_3_905_0,
     author = {Delorme, Charles and Heydemann, Marie-Claude},
     title = {On a problem of walks},
     journal = {Annales de l'Institut Fourier},
     pages = {905--919},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {49},
     number = {3},
     year = {1999},
     doi = {10.5802/aif.1698},
     mrnumber = {2000h:05096},
     zbl = {0922.05031},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/aif.1698/}
}
TY  - JOUR
AU  - Delorme, Charles
AU  - Heydemann, Marie-Claude
TI  - On a problem of walks
JO  - Annales de l'Institut Fourier
PY  - 1999
SP  - 905
EP  - 919
VL  - 49
IS  - 3
PB  - Association des Annales de l’institut Fourier
UR  - http://www.numdam.org/articles/10.5802/aif.1698/
DO  - 10.5802/aif.1698
LA  - en
ID  - AIF_1999__49_3_905_0
ER  - 
%0 Journal Article
%A Delorme, Charles
%A Heydemann, Marie-Claude
%T On a problem of walks
%J Annales de l'Institut Fourier
%D 1999
%P 905-919
%V 49
%N 3
%I Association des Annales de l’institut Fourier
%U http://www.numdam.org/articles/10.5802/aif.1698/
%R 10.5802/aif.1698
%G en
%F AIF_1999__49_3_905_0
Delorme, Charles; Heydemann, Marie-Claude. On a problem of walks. Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 905-919. doi : 10.5802/aif.1698. http://www.numdam.org/articles/10.5802/aif.1698/

[1] L. W. Beineke, On derived graphs and digraphs, in Beiträge zur Graphentheorie (ed. Sachs et al.), Teubner-Verlag, Leipzig (1968), 17-23. | Zbl

[2] C. Berge, Graphes et Hypergraphes, Dunod, Paris, 1973. | MR | Zbl

[3] M. A. Fiol, J. L. A. Yebra, and I. Alegre, Line digraph iterations and the (d, k) digraph problem, IEEE Transactions on Computers, C-33(5) (1984), 400-403. | Zbl

[4] C. D. Godsil, Algebraic combinatorics, Chapman and Hall, New-York, 1993. | MR | Zbl

[5] F. Harary and R. Z. Norman, Some properties of line digraphs, Rend. Circ. Mat. Palermo, (2) 9 (1960), 161-168. | MR | Zbl

[6] R. L. Hemminger, Digraphs with periodic line digraphs, Studia Sci. Math. Hungar., 9 (1974), 27-31. | MR | Zbl

[7] R. L. Hemminger and L. W. Beineke, Line graphs and line digraphs, in Selected topics in graph theory I (1983), 270-304. | Zbl

[8] H. Minc, Nonnegative matrices, J. Wiley and Sons (New York), Wiley-interscience series in discrete mathematics and optimization, 1988. | MR | Zbl

[9] P. Tvrdík, R. Harbane, M.-C. Heydemann, Uniform Homomorphisms and Divide & Conquer Emulations on de Bruijn and Kautz Networks, Discrete Appl. Math., 83 (1998), 279-301. | MR | Zbl

[10] H. S. Wilf, Generatingfunctionology, Academic Press, New York, 1990. | MR | Zbl

Cité par Sources :