Enumerative applications of a decomposition for graphs and digraphs

DOI10.1016/0012-365X(94)00135-6zbMath0827.05045OpenAlexW2073359459MaRDI QIDQ1893989

Ira M. Gessel

Publication date: 27 November 1995

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(94)00135-6

zbMATH Keywords

generating functionsconnected componentsdecompositiondigraphstreesTutte polynomialcomplete graphcounting graphsinversion enumeator

Mathematics Subject Classification ID

Trees (05C05) Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Directed graphs (digraphs), tournaments (05C20)

Related Items (20)

On the Tutte and Matching Polynomials for Complete Graphs ⋮ Macdonald cumulants, \(G\)-inversion polynomials and \(G\)-parking functions ⋮ Parking functions and tree inversions revisited ⋮ On sequences of polynomials arising from graph invariants ⋮ Counting acyclic digraphs by sources and sinks ⋮ An insertion algorithm on multiset partitions with applications to diagram algebras ⋮ A combinatorial link between labelled graphs and increasingly labelled Schröder trees ⋮ Exact enumeration of satisfiable 2-SAT formulae ⋮ Trees, parking functions, and standard monomials of skeleton ideals ⋮ Counting acyclic and strong digraphs by descents ⋮ Generating functions of some families of directed uniform hypergraphs ⋮ Unnamed Item ⋮ Cayley compositions, partitions, polytopes, and geometric bijections ⋮ \(G\)-parking functions and tree inversions ⋮ Triangulations of Cayley and Tutte polytopes ⋮ Trees, parking functions and factorizations of full cycles ⋮ Möbius coinvariants and bipartite edge-rooted forests ⋮ Unnamed Item ⋮ Flow Polytopes and the Space of Diagonal Harmonics ⋮ LLT cumulants and graph coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Depth-first search as a combinatorial correspondence
• Une famille de polynômes ayant plusieurs propriétés enumeratives
• Nombres d'Euler et inversions dans les arbres
• On external activity and inversions in trees
• The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions
• A Noncommutative Generalization and q-Analog of the Lagrange Inversion Formula
• Enumeration of trees by inversions
• The inversion enumerator for labeled trees
• A Contribution to the Theory of Chromatic Polynomials

This page was built for publication: Enumerative applications of a decomposition for graphs and digraphs