A characterization of the Tutte polynomial via combinatorial embeddings

Details A characterization of the Tutte polynomial via combinatorial embeddings A characterization of the Tutte polynomial via combinatorial embeddings

2006-08-02

arxiv.org/abs/math/0608057v1

Annals of Combinatorics 12, 2 (2008) 139-153

Mathematics

Combinatorics

14 pages

Scientific paper

We give a new characterization of the Tutte polynomial of graphs. Our characterization is formally close (but inequivalent) to the original definition given by Tutte as the generating function of spanning trees counted according to activities. Tutte's notion of activity requires to choose a \emph{linear order} on the edge set (though the generating function of the activities is, in fact, independent of this order). We define a new notion of activity, the embedding-activity, which requires to choose a \emph{combinatorial embedding} of the graph, that is, a cyclic order of the edges around each vertex. We prove that the Tutte polynomial equals the generating function of spanning trees counted according to embedding-activities (this generating function being, in fact, independent of the embedding).

Affiliated with

Also associated with

No associations

Rating

A characterization of the Tutte polynomial via combinatorial embeddings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A characterization of the Tutte polynomial via combinatorial embeddings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A characterization of the Tutte polynomial via combinatorial embeddings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-265083