Series-parallel posets and the Tutte polynomial
type: Item
instance of: scholarly article
title: Series-parallel posets and the Tutte polynomial
zbMATH Open document ID: 0859.06001
DOI: 10.1016/0012-365X(95)00037-W
author: Gary Gordon
published in: Discrete Mathematics
publication date: 1996-11-07T00:00:00Z
review text: Let \(P\) a poset and let \(I \subseteq P\). Then \(I\) is an order ideal if whenever \(x\in I\) and \(x>y\), then \(y\in I\). For \(S \subseteq P\), define the rank of \(S\), denoted \(r_p(S)\) (or simply \(r(S))\) as follows: \[ r_p (S)= \max_{I \subseteq S} \bigl\{|I |: I \text{ is an order ideal} \bigr\}. \] The Tutte polynomial of \(P\) is defined by \[ f(P; t,z) = \sum_{S \subseteq P} t^{|P|-r(S)} z^{|S |-r(S)}. \] The scope of this paper is to study the Tutte polynomial \(f(P;t,z)\) of a series-parallel partially ordered set \(P\). The author shows that \(f(P)\) can be computed in polynomial time when \(P\) is series-parallel and that series-parallel posets having isomorphic deletions and contractions are themselves isomorphic. A formula for \(f(P^*)\) in terms of \(f(P)\) is obtained and shows that these two polynomials factor over \(Z[t,z]\) in the same way. Also, the author examines several subclasses of the class of series-parallel posets, proving that \(f(P)\neq f(Q)\) for non-isomorphic \(P\) and \(Q\) in the largest of these classes.
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 943219
zbMATH Keywords: order ideal
zbMATH Keywords: Tutte polynomial
zbMATH Keywords: series-parallel posets
reviewed by: Dimitru Buşneag
MaRDI profile type: Publication
cites work: Introduction to Greedoids
cites work: Q4012032
cites work: Tutte polynomials for trees
cites work: The complexity of computing the Tutte polynomial on transversal matroids
cites work: Searching in Trees, Series-Parallel and Interval Orders
cites work: A Tutte polynomial for partially ordered sets
cites work: A Greedoid Polynomial Which Distinguishes Rooted Arborescences
cites work: On the computational complexity of the Jones and Tutte polynomials
cites work: On the greedoid polynomial for rooted graphs and rooted digraphs
cites work: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
cites work: Enumeration of Posets Generated by Disjoint Unions and Ordinal Sums
cites work: Q3748279
cites work: The Recognition of Series Parallel Digraphs
cites work: The Complexity of Enumeration and Reliability Problems
description: scientific article; zbMATH DE number 943219