Graphe chenille

thumb|upright=1.2|Un graphe chenille. En théorie des graphes, un graphe chenille ou plus simplement une chenille est un arbre dans lequel tous les sommets sont à distance au plus 1 d'un chemin central. Les graphes chenilles ont d'abord été étudiés dans une série d'articles de Harary et Schwenk. Le nom a été suggéré par A. Hobbs. Harary & Schwenk écrivent de façon colorée : « une chenille est un arbre qui se métamorphose en un chemin lorsque son cocon de points d'extrémité est supprimé ». Les graphes chenille possèdent un étiquetage gracieux. Les caractérisations suivantes décrivent les chenilles: Les chenilles sont les arbres pour lesquels la suppression des feuilles et des arêtes incidentes produit un graphe chemin. les arbres dans lesquels il existe un chemin qui contient tous les sommets de degré deux ou plus. les arbres dans lesquels chaque sommet de degré au moins trois a au plus deux voisins qui ne sont pas des feuilles. les arbres qui ne contiennent pas comme sous-graphe le graphe obtenu en remplaçant chaque arête du graphe étoile K 1,3 par un chemin de longueur deux. les graphes connexes qui peuvent être tracés avec leurs sommets sur deux droites parallèles, avec des arêtes représentées par des segments de droites sans croisement qui ont un point d'extrémité sur chacune des droites. les arbres dont le carré est une chaîne hamiltonienne. En d'autres termes dans une chenille, il existe une séquence cyclique de tous les sommets dans laquelle chaque paire de sommets consécutifs est à distance un ou deux l'une de l'autre, et les arbres qui ne sont pas des chenilles ne possèdent pas une telle séquence. Un cycle de ce type peut être obtenu en traçant la chenille sur deux droites parallèles et en concaténant la séquence de sommets sur une droite avec l'inverse de la séquence sur l'autre droite . les arbres dont le line graph contient une chaîne hamiltonienne ; une telle chaîne peut être obtenu en ordonnant les arêtes dans un dessin à deux droites de l'arbre.