Tutte polynomials for directed graphs

DOI10.1016/J.JCTB.2019.05.006MaRDI QIDQ2284730zbMATH OpenOpenAlexWikidataFDO

Authors Jordan Awan, Olivier Bernardi

Publication date 15 January 2020

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

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

zbMATH Keywords

chromatic polynomial of mixed graphschromatic symmetric functioncombinatorial reciprocitydigraph generating functionsdigraph invariantPotts model for digraphsquasisymmetric functions

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Directed graphs (digraphs), tournaments (05C20) Graph polynomials (05C31) Symmetric functions and generalizations (05E05)

Abstract: The Tutte polynomial is a fundamental invariant of graphs. In this article, we define and study a generalization of the Tutte polynomial for directed graphs, that we name B-polynomial. The B-polynomial has three variables, but when specialized to the case of graphs (that is, digraphs where arcs come in pairs with opposite directions), one of the variables becomes redundant and the B-polynomial is equivalent to the Tutte polynomial. We explore various properties, expansions, specializations, and generalizations of the B-polynomial, and try to answer the following questions: 1. what properties of the digraph can be detected from its B-polynomial (acyclicity, length of paths, number of strongly connected components, etc.)? 2. which of the marvelous properties of the Tutte polynomial carry over to the directed graph setting? The B-polynomial generalizes the strict chromatic polynomial of mixed graphs introduced by Beck, Bogart and Pham. We also consider a quasisymmetric function version of the B-polynomial which simultaneously generalizes the Tutte symmetric function of Stanley and the quasisymmetric chromatic function of Shareshian and Wachs.

Recommendations

• Digraph analogues of the Tutte polynomial
• scientific article; zbMATH DE number 617570
• On the cover polynomial of a digraph
• Universal Tutte polynomial
• Graph polynomials and their applications. I: The Tutte polynomial

Cites work

• A symmetric function generalization of the chromatic polynomial of a graph
• A weighted graph polynomial from chromatic invariants of knots
• Acyclic orientations of graphs
• Chromatic quasisymmetric functions
• Convexity in oriented matroids
• Convolution-multiplication identities for Tutte polynomials of graphs and matroids
• Enumeration of Golomb rulers and acyclic orientations of mixed graphs
• Equality of \(P\)-partition generating functions.
• Fourientation activities and the Tutte polynomial
• Fourientations and the Tutte polynomial
• Generalized activities and the Tutte polynomial
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• scientific article; zbMATH DE number 53152 (Why is no real title available?)
• scientific article; zbMATH DE number 3545685 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 617570 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3341135 (Why is no real title available?)
• Inside-out polytopes
• Interval partitions and activities for the greedoid Tutte polynomial
• Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars
• On distinguishing trees by their chromatic symmetric functions
• On the cover polynomial of a digraph
• On trees with the same restricted \(U\)-polynomial and the Prouhet-Tarry-Escott problem
• Ordered structures and partitions
• Partial graph orientations and the Tutte polynomial
• Proper caterpillars are distinguished by their chromatic symmetric function
• Scheduling Problems and Mixed Graph Colorings
• The Potts model and the Tutte polynomial.
• The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions

Cited in

(22)

• On an ordering-dependent generalization of the Tutte polynomial
• \#P-completeness of counting update digraphs, cacti, and series-parallel decomposition method
• Universal Tutte polynomial
• The Hopf monoid and the basic invariant of directed graphs
• Higher matrix-tree theorems and Bernardi polynomial
• The drop polynomial of a weighted digraph
• Directed Graphs and the Jacobi-Trudi Identity
• scientific article; zbMATH DE number 617570 (Why is no real title available?)
• The Tutte polynomial and toric Nakajima quiver varieties
• Interlace polynomials of lollipop and tadpole graphs
• Digraph analogues of the Tutte polynomial
• Tutte polynomials for regular oriented matroids
• Polynomial invariants for cactuses
• Tutte polynomial of tensor product graph and its applications
• Partial graph orientations and the Tutte polynomial
• Coplanarity of rooted spanning-tree vectors
• Distinguishing and reconstructing directed graphs by their B-polynomials
• Eulerian polynomials for digraphs
• Coefficients of the Tutte polynomial and minimal edge cuts of a graph
• An equality for balanced digraphs
• Eulerian polynomials for digraphs
• A Tutte polynomial for signed graphs

This page was built for publication: Tutte polynomials for directed graphs

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