Graphe chenille

Les graphes chenilles^[1] 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^[2],[3]. 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é »^[2]. 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^[3],[4].
• les arbres dans lesquels il existe un chemin qui contient tous les sommets de degré deux ou plus^[4],[5].
• 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^[4].
• 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. Plus généralement, le nombre d'arêtes qui doivent être ajoutées au line graph d'un arbre arbitraire pour qu'il contienne une chaîne hamiltonienne (la taille de sa complétion hamiltonienne ) est égal au nombre minimum de décompositions de l'arbre en chenilles à arêtes disjointes^[6].
• les graphes connexes de largeur de chemin égale à un^[7].
• les graphes d'intervalle sans triangle et connexes^[8].

Un k-arbre est un graphe cordal avec exactement n-k cliques maximales, chacune contenant k+1 sommets; dans un k-arbre qui n'est pas lui-même une clique de k+1 sommets, chaque clique maximale sépare le graphe en deux ou plusieurs composantes, ou alors elle contient un seul sommet feuille, un sommet qui n'appartient qu'à une seule clique maximale. Une k-chaîne est un k-arbre avec au plus deux feuilles, et une k- chenille est un k-arbre qui peut être décomposé en une k-chaîne et des k-feuilles, chacune adjacente à un séparateur qui est une k-clique de la k-chaîne. Dans cette terminologie, une 1-chenille est la même chose qu'un arbre à chenilles, et les k-chenilles sont les graphes maximaux en nombre d'arêtes avec largeur de chemin égale à k^[7].

Un graphe homard est un arbre dans lequel tous les sommets sont à distance 2 d'un chemin central^[9].

Les chenilles forment une famille de graphes pour laquelle une formule exacte peut être donnée : pour n ≥ 3, le nombre de chenilles à n sommets non étiquetés est :

${\displaystyle 2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.}$

Pour n = 1, 2, 3, ... les nombres de chenilles à n sommets est

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, ...

C'est la suite A005418 de l'OEIS .