Parity, Eulerian subgraphs and the Tutte polynomial

DOI10.1016/J.JCTB.2007.09.006MaRDI QIDQ2483482zbMATH OpenOpenAlexFDO

Authors Andrew Goodall

Publication date 28 April 2008

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

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

zbMATH Keywords

Fourier transformcorrelationweight enumeratorTutte polynomialparityEulerian subgraphs

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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)