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 such that for any integer , has exactly walks of length , where is the order of . 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.
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 tels que pour tout entier , ait exactement chemins de longueur , où est l’ordre de . 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.
@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}, zbl = {0922.05031}, mrnumber = {2000h:05096}, language = {en}, url = {https://aif.centre-mersenne.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 - https://aif.centre-mersenne.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 https://aif.centre-mersenne.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, Volume 49 (1999) no. 3, pp. 905-919. doi : 10.5802/aif.1698. https://aif.centre-mersenne.org/articles/10.5802/aif.1698/
[1] On derived graphs and digraphs, in Beiträge zur Graphentheorie (ed. Sachs et al.), Teubner-Verlag, Leipzig (1968), 17-23. | Zbl
,[2] Graphes et Hypergraphes, Dunod, Paris, 1973. | MR | Zbl
,[3] Line digraph iterations and the (d, k) digraph problem, IEEE Transactions on Computers, C-33(5) (1984), 400-403. | Zbl
, , and ,[4] Algebraic combinatorics, Chapman and Hall, New-York, 1993. | MR | Zbl
,[5] Some properties of line digraphs, Rend. Circ. Mat. Palermo, (2) 9 (1960), 161-168. | MR | Zbl
and ,[6] Digraphs with periodic line digraphs, Studia Sci. Math. Hungar., 9 (1974), 27-31. | MR | Zbl
,[7] Line graphs and line digraphs, in Selected topics in graph theory I (1983), 270-304. | Zbl
and ,[8] Nonnegative matrices, J. Wiley and Sons (New York), Wiley-interscience series in discrete mathematics and optimization, 1988. | MR | Zbl
,[9] Uniform Homomorphisms and Divide & Conquer Emulations on de Bruijn and Kautz Networks, Discrete Appl. Math., 83 (1998), 279-301. | MR | Zbl
, , ,[10] Generatingfunctionology, Academic Press, New York, 1990. | MR | Zbl
,Cited by Sources: