Isomorphism of Weighted Trees and Stanley's Conjecture for Caterpillars

Isomorphismes d'arbres pondérés et la conjecture de Stanley pour les chenilles.

Martin Loebl (1) , Jean-Sébastien Sereni (2, 3)

1 KAM - Department of Applied Mathematics (KAM)
2 ORPAILLEUR - Knowledge representation, reasonning
3 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications

We show that the $W$-polynomial distinguishes non-isomorphic weighted trees of a \emph{good} family. The framework developed to do so also allows us to show that the $W$-polynomial distinguishes non-isomorphic caterpillars. This establishes Stanley's conjecture for caterpillars, an extensively studied problem.

Nous démontrons que le polynôme~$W$ distingue les arbres pondérés non-isomorphes au sein d'une \emph{bonne} famille. Le cadre de travail développé nous permet de démontrer que le polynôme~$W$ distingue les chenilles non-isomorphes. Ceci établit la conjecture de Stanley pour les chenilles, un problème grandement étudié.

Mots clés: graph reconstruction; graph isomorphism; U-polynomial; tree; Stanley's conjecture

Domaines: Combinatoire [math.CO]

Martin Loebl, Jean-Sébastien Sereni. Isomorphism of Weighted Trees and Stanley's Conjecture for Caterpillars. 2017. ⟨hal-00992104v3⟩