Graphe à distance héréditaire

vignette| Exemple d'un graphe à distance héréditaire. En théorie des graphes, un graphe à distance héréditaire (aussi appelé graphe complètement séparable) est un graphe dans lequel les distances entre sommets dans tout sous-graphe induit connexe sont les mêmes que celles du graphe tout entier ; autrement dit, tout sous-graphe induit hérite les distances du graphe entier. Les graphes à distance héréditaire ont été nommés et étudiés pour la première fois par Howorka en 1977, alors qu'une classe équivalente de graphes a déjà été considérée en 1970 par Olaru et Sachs qui ont montré que ce sont des graphes parfaits. Les graphes à distance héréditaire constituent une classe de graphes d'intersection ; un modèle d'intersection a été donné par Gioan et Paul en 2012. La définition originale d'un graphe à distance héréditaire est la suivante : c'est un graphe G tel que, pour deux sommets u et v appartenant à un sous-graphe induit connexe H de G, un plus court chemin reliant u et v dans G est contenu dans H, de sorte que la distance entre u et v dans H est la même que la distance dans G. Les graphes à distance héréditaire peuvent être caractérisés de plusieurs autres manières équivalentes : Ce sont les graphes dans lesquels tout chemin induit est un chemin le plus court, ou de manière équivalente les graphes dans lesquels tout chemin qui n'est pas de longueur minimale a au moins une arête reliant deux sommets non consécutifs du chemin. Ce sont les graphes dans lesquels chaque cycle de longueur ≥ 5 a au moins deux diagonales qui se croisent. Ce sont les graphes dans lesquels, pour quatre sommets quelconques, deux au moins des trois sommes de distances , et sont égales. Ce sont les graphes qui n'ont pas de sous-graphe isométrique qui est un cycle de longueur ≥ 5, ou l'un des trois graphes suivants : un cycle à 5 sommets avec une corde, un cycle à 5 sommets avec deux cordes qui ne se croisent pas, et un cycle à 6 sommets avec une corde reliant des sommets opposés. vignette|upright=1.5| Les trois opérations qui permettent de construire tout graphe distance-héréditaire.