Parity, Eulerian subgraphs and the Tutte polynomial

DOI10.1016/J.JCTB.2007.09.006zbMATH Open1162.05019arXiv0707.2306OpenAlexW2021450686MaRDI QIDQ2483482FDOQ2483482

Authors: Andrew Goodall 

Publication date: 28 April 2008

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/0707.2306

Recommendations

• Parametrized Tutte Polynomials of Graphs and Matroids
• Parity equivalence in eulerian graphs
• The Tutte polynomial for graphs
• Tutte polynomial of some multigraphs
• Congruence conditions, parcels, and Tutte polynomials of graphs and matroids
• On graphs determined by their Tutte polynomials
• scientific article; zbMATH DE number 5247088
• The Tutte polynomial of the Sierpiński and Hanoi graphs
• Ehrhart polynomial and arithmetic Tutte polynomial
• On the Tutte and Matching Polynomials for Complete Graphs

zbMATH Keywords

Fourier transformcorrelationweight enumeratorTutte polynomialparityEulerian subgraphs

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorial Nullstellensatz
• Map coloring and the vector cross product
• List edge colourings of some 1-factorable multigraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Colorings and orientations of graphs
• The number of edge 3-colorings of a planar cubic graph as a permanent
• Title not available (Why is that?)
• Fourier analysis on finite abelian groups: some graphical applications
• On the Principal Edge Tripartition of a Graph
• Some new evaluations of the Tutte polynomial
• Some probabilistic restatements of the Four Color Conjecture
• Coboundaries, flows, and Tutte polynomials of matrices
• The graph polynomial and the number of proper vertex colorings
• A note on graph colorings and graph polynomials
• Nowhere-zero flow polynomials
• Support weight enumerators and coset weight distributions of isodual codes

Cited In (9)

• The parity problem of polymatroids without double circuits
• On the evaluation at (3,3) of the Tutte polynomial of a graph
• One More Probabilistic Reformulation of the Four Colour Conjecture
• Congruence conditions, parcels, and Tutte polynomials of graphs and matroids
• Evaluations of Graph Polynomials
• A parity result of Fraysseix, computational complexity of Tutte polynomials, and a conjecture on planar graphs
• Fourientations and the Tutte polynomial
• Flows and colorings
• Connection Matrices for MSOL-Definable Structural Invariants

This page was built for publication: Parity, Eulerian subgraphs and the Tutte polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2483482)