On a problem of walks
Delorme, Charles ; Heydemann, Marie-Claude
Annales de l'Institut Fourier, Tome 49 (1999), p. 905-919 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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},
     volume = {49},
     year = {1999},
     pages = {905-919},
     doi = {10.5802/aif.1698},
     mrnumber = {2000h:05096},
     zbl = {0922.05031},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_1999__49_3_905_0}
}

Delorme, Charles; Heydemann, Marie-Claude. On a problem of walks. Annales de l'Institut Fourier, Tome 49 (1999) pp. 905-919. doi : 10.5802/aif.1698. http://gdmltest.u-ga.fr/item/AIF_1999__49_3_905_0/

[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 0179.29204

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

[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 0528.68048

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

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

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

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

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

[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 99d:68025 | Zbl 0902.68078

[10] H. S. Wilf, Generatingfunctionology, Academic Press, New York, 1990. | MR 91g:05008 | Zbl 0689.05001