The EMS Publishing House is now EMS Press and has its new home at ems.press.

Please find all EMS Press journals and articles on the new platform.

Annales de l’Institut Henri Poincaré D


Full-Text PDF (288 KB) | Metadata | Table of Contents | AIHPD summary
Volume 6, Issue 3, 2019, pp. 357–384
DOI: 10.4171/AIHPD/74

Published online: 2019-05-07

Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars

Martin Loebl[1] and Jean-Sébastien Sereni[2]

(1) Charles University, Prague, Czechia
(2) Centre National de la Recherche Scientifique, Strasbourg, France

This paper contributes to a programme initiated by the first author: "How much information about a graph is revealed in its Potts partition function?“ We show that the $W$-polynomial distinguishes non-isomorphic weighted trees of a 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.

Keywords: $W$-polynomial, tree, graph reconstruction, graph isomorphism, $U$-polynomial, Stanley’s isomorphism conjecture, Potts partition function

Loebl Martin, Sereni Jean-Sébastien: Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 6 (2019), 357-384. doi: 10.4171/AIHPD/74