No document available.
Abstract :
[fr] Étant donné un graphe G, nous nous intéressons au nombre L(i) qui est le nombre maximum de feuilles qu'un sous-arbre induit de taille i peut posséder. Dans ce contexte, nous introduisons le problème de "réalisation" qui consiste à determiner si, pour une suite donnée d'entiers (k_0,k_1,...,k_n), il existe un graphe G à n sommets tel que k_i = L(i) pour tout i entre 0 et n.
Dans cet exposé, nous présentons une réponse partielle à ce problème en nous restreignant à l'ensemble des graphes chenilles. Les suites d'entiers qui sont réalisées par des graphes chenilles sont en lien avec une famille de mots binaires, connus sous le nom de mots préfixes normaux. Ces mots sont définis par le fait que leurs préfixes contiennent au moins autant de 1 que n'importe quel facteur de même longueur.