Graph Tower Dichromatic Polynomial

Niveau: Supérieur, Licence, Bac+3
Graph Tower Dichromatic Polynomial Olivier Ramare UMR CNRS 8524 Universite de Lille I F-59655 - Villeneuve d'Ascq - France Daniel Tanre UMR CNRS 8524 Universite de Lille I F-59655 - Villeneuve d'Ascq - France March 25, 2008 Abstract Starting from a non-oriented graph G and an integer s, we define the graph tower G(s). In the linear graph G = Lr case, this results in the classical square on r ? s vertices. The aim of this paper is to describe an effective method to compute this dichromatic polyno- mial ZG(s)(q, v) and to prove rationality of the series ?G(q, v)[X] =∑ s≥1 ZG(s)(q, v)X s?1. The functionals created for this purpose are implemented using MuPAD and may be obtained under GPL licence. 1 Dichromatic Polynomial. Let us begin with the definition of the dichromatic polynomial as can be found in [3, Chapter X] or [2]. Connection-contraction principle: The dichromatic polynomial of a (non ori- ented) graph G = (V,E) is a two variables polynomial, denoted by Z(G) or ZG(q, v) if we need this specification.

• oriented graph


• statistical mechanics


• tower


• graph towers


• xa


• edges between


• output variable


• dichromatic polynomial