Quelques propriétés des graphes distances héréditaires

Dans cette étude de quelques propriétés des graphes distances héréditaires, nous donnons principalement deux algorithmes linéaires de reconnaissance des graphes distances héréditaires. Ces algorithmes sont important étant du fait que le seul algorithme linéaire de reconnaissance existant à notre connaissance [Hammer-Maffray90] n'était pas complet, et que certains algorithmes utilisent comme outil la reconnaissance de ces graphes en linéaire. Nous introduisons également la notion de séquence d'élagage qui est intéressante, car elle nous donne un codage efficace de ces graphes. L'étude des propriétés de l'arbre de décomposition par substitution nous permet d'avoir un autre algorithme de reconnaissance, qui bien que non linéaire a l'avantage d'être très simple. De plus, cet algorithme peut, avec pas beaucoup de modification, être utilisé pour calculer le graphe réduit d'un graphe quelconque pour les opérations de destruction des sommets pendants et contraction des sommets jumeaux.