Parity, eulerian subgraphs and the Tutte polynomial

Details Parity, eulerian subgraphs and the Tutte polynomial Parity, eulerian subgraphs and the Tutte polynomial

2007-07-16

arxiv.org/abs/0707.2306v2

Mathematics

Combinatorics

31 pages

Scientific paper

Identities obtained by elementary finite Fourier analysis are used to derive a variety of evaluations of the Tutte polynomial of a graph G at certain points (a,b) where (a-1)(b-1) equals 2 or 4. These evaluations are expressed in terms of eulerian subgraphs of G and the size of subgraphs modulo 2,3,4 or 6. In particular, a graph is found to have a nowhere-zero 4-flow if and only if there is a correlation between the event that three subgraphs A,B,C chosen uniformly at random have pairwise eulerian symmetric differences and the event that the integer part of (|A| + |B| + |C|) / 3 is even. Some further evaluations of the Tutte polynomial at points (a,b) where (a-1)(b-1) = 3 are also given that illustrate the unifying power of the methods used. The connection between results of Matiyasevich, Alon and Tarsi and Onn is highlighted by indicating how they may all be derived by the techniques adopted in this paper.

Affiliated with

Also associated with

No associations

Rating

Parity, eulerian subgraphs and the Tutte polynomial 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 Parity, eulerian subgraphs and the Tutte polynomial, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parity, eulerian subgraphs and the Tutte polynomial will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-195136