Homomorphisms and polynomial invariants of graphs

Description

This paper initiates a general study of the connection between graph homomorphisms and the Tutte polynomial. This connection can be extended to other polynomial invariants of graphs related to the Tutte polynomial such as the transition, the circuit partition, the boundary, and the coboundary polynomials. As an application, we describe in terms of homomorphism counting some fundamental evaluations of the Tutte polynomial in abelian groups and statistical physics. We conclude the paper by providing a homomorphism view of the uniqueness conjectures formulated by Bollobás, Pebody and Riordan.

Abstract

Ministerio de Educación y Ciencia MTM2005-08441-C02-01

Abstract

Junta de Andalucía PAI-FQM-0164

Abstract

Junta de Andalucía P06-FQM-01649

Additional details