Parity, eulerian subgraphs and the Tutte polynominal

AJ Goodall

Research output: Contribution to journalArticle (Academic Journal)peer-review

4 Citations (Scopus)

Abstract

Identities obtained by elementary finite Fourier analysis are used to derive a variety of evaluations of the Tutte polynomial of a graph G on the hyperbolae H_2 and H_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. Further, 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.
Translated title of the contributionParity, eulerian subgraphs and the Tutte polynominal
Original languageEnglish
Pages (from-to)599 - 628
Number of pages30
JournalJournal of Combinatorial Theory Series B
Volume98
Issue number3
DOIs
Publication statusPublished - May 2008

Bibliographical note

Publisher: Elsevier
Other: http://arxiv.org/abs/0707.2306

Fingerprint Dive into the research topics of 'Parity, eulerian subgraphs and the Tutte polynominal'. Together they form a unique fingerprint.

Cite this