Total exchange, broadcasting and some results on iterated line digraphs

Description

We deal with global communication on connected graphs. First, we consider the case of the total exchange. The minimum total exchange time (M.T.E.T.) is the minimum number of steps required to fully inform all the vertices. We establish new bounds (lower and upper) on the M.T.E.T. We determine the M.T.E.T. of the trees and more generally of the graphs whose minimum degree is one. We prove a conjecture of Bermond, Kodate, Marlin, and Perennes on the fixed points of a complete rotation of some toroidal meshes, and deduce the optimality of their M.T.E.T. We prove also that the M.T.E.T. of a directed De Bruijn graph is optimal. In a second part, we consider the classical broadcast problem. We determine a new upper bound on the broadcast time of an undirected graph, depending of its connectivity. We caractherize some graphs having the same matching number and minimum degree and give their broadcast time. We give new results on the broadcast in De Bruijn graphs. In the last part, we give original results on the independence number of a de Bruijn graph and more generally on the independence number of iterated line digraphs. Then, we prove that the minimum size of a quasi center of a De Bruijn graph UB(d, D) is d - 1, which validates a first conjecture of Bond. At last, we prove that the radius of a Kautz graph UK(2, D) is D, which validates a second conjecture of Bond.

Abstract (French)

Nous nous intéressons à des protocoles de communications globales portant sur les graphes connexes. Dans une première partie, nous considérons le cas de l'échange total. Le Temps Minimum d'Echange Total (T.M.E.T.) est le nombre minimum d'étapes nécessaires pour que tous les sommets reçoivent tous les messages. Nous établissons des nouvelles bornes (inférieures et supérieures) sur le T.M.E.T. Nous déterminons le T.M.E.T des arbres et plus généralement des graphes de degré minimum un. Nous démontrons une conjecture de Bermond, Kodate, Marlin et Perennes sur les points fixes d'une rotation complète de certaines grilles toriques, ce qui permet de déduire l'optimalité de leur T.M.E.T. Nous montrons aussi que le T.M.E.T d'un graphe orienté de de Bruijn est optimal. Dans une seconde partie, nous considérons la problème classique de la diffusion. Nous déterminons une nouvelle borne supérieure sur le temps de diffusion d'in graphe non orienté en fonction de sa connectivité. Nous caractérisons certains graphes dont le numéro de couplage est égal au degré minimum et déterminons leur temps de diffusion. Nous donnons des résultats nouveaux sur la diffusion dans les graphes de de Bruijn. Dans la dernière partie, nous donnons des résultats originaux sur le nombre de stabilité d'un graphe de de Bruijn et plus généralement des graphes représentatifs des arcs. Nous montrons ensuite que la taille minimum d'un graphe de de Bruijn UB est ce qui valide une première conjecture de Bond. Enfin, nous prouvons que le rayon d'un graphe de Kautz est D, ce qui valide une seconde conjecture de Bond. ( d ,D ) d 1, - 2 UK( ,D )

Additional details