Annales de l’Institut Henri Poincaré D
Full-Text PDF (288 KB) | Metadata | Table of Contents | AIHPD summary
Published online: 2019-05-07
Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillarsMartin Loebl and Jean-Sébastien Sereni (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