%0 Journal Article
%T The Tutte-Grothendieck Group of an Alphabetic Rewriting System
%A Laurent Poinsot
%J ISRN Combinatorics
%D 2013
%R 10.1155/2013/574578
%X The two operations, deletion and contraction of an edge, on multigraphs directly lead to the Tutte polynomial which satisfies a universal problem. As observed by Brylawski (1972) in terms of order relations, these operations may be interpreted as a particular instance of a general theory which involves universal invariants like the Tutte polynomial and a universal group, called the Tutte-Grothendieck group. In this contribution, Brylawski¡¯s theory is extended in two ways: first of all, the order relation is replaced by a string rewriting system, and secondly, commutativity by partial commutations (that permits a kind of interpolation between noncommutativity and full commutativity). This allows us to clarify the relations between the semigroup subject to rewriting and the Tutte-Grothendieck group: the latter is actually the Grothendieck group completion of the former, up to the free adjunction of a unit (this was not even mentioned by Brylawski), and normal forms may be seen as universal invariants. Moreover we prove that such universal constructions are also possible in case of a nonconvergent rewriting system, outside the scope of Brylawski¡¯s work. 1. Introduction In his paper [1], Tutte took advantage of two natural operations on (finite multi) graphs (actually on isomorphism classes of multigraphs), deletion and contraction of an edge, in order to introduce the ring and a polynomial in two commuting variables , also known by Whitney [2], unique up to isomorphism since solutions of a universal problem. This polynomial, since called the Tutte polynomial, is a graph invariant in at least two different meanings: first of all, it is defined on isomorphism classes, rather than on actual graphs, in such a way that two graphs with distinct Tutte polynomials are not isomorphic (a well-known functorial point of view), and, secondly, it is invariant with respect to a graph decomposition. Indeed, let be a graph, and let be an edge of , which is not a loop (an edge with the same vertex as source and target) nor a bridge (an edge that connects two connected components of a graph). The edge contraction of is the graph obtained by identifying the vertices source and target of , and removing the edge . We write for the graph where the edge is merely removed; this operation is the edge deletion. Let us consider the graph (well-defined as isomorphic classes) which can be interpreted as a decomposition of . Then, the Tutte polynomial is invariant with respect to this decomposition in the sense that . Moreover this decomposition eventually terminates with graphs with
%U http://www.hindawi.com/journals/isrn.combinatorics/2013/574578/