✦ LIBER ✦

Enumerative applications of a decomposition for graphs and digraphs

✍ Scribed by Ira M. Gessel

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 650 KB
Volume: 139
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00135-6

No coin nor oath required. For personal study only.

✦ Synopsis

A simple decomposition for graphs yields generating functions for counting graphs by edges and connected components. A change of variables gives a new interpretation to the Tutte polynomial of the complete graph involving inversions of trees. The relation between the Tutte polynomial of the complete graph and the inversion enumerator for trees is generalized to the Tutte polynomial of an arbitrary graph. When applied to digraphs, the decomposition yields formulas for counting digraphs and acyclic digraphs by edges and initially connected components.

📜 SIMILAR VOLUMES

Optimal Orientations of Graphs and Digra

Optimal Orientations of Graphs and Digraphs: A Survey

✍ K.M. Koh; E.G. Tay 📂 Article 📅 2002 🏛 Springer Japan 🌐 English ⚖ 132 KB

The connectivity of large digraphs and g

The connectivity of large digraphs and graphs

✍ M. A. Fiol 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 632 KB

## Abstract This paper studies the relation between the connectivity and other parameters of a digraph (or graph), namely its order __n__, minimum degree δ, maximum degree Δ, diameter __D__, and a new parameter l~pi;~, __0__ ≤ π ≤ δ − 2, related with the number of short paths (in the case of graphs

Connectivity of large bipartite digraphs

Connectivity of large bipartite digraphs and graphs

✍ M.C. Balbuena; A. Carmona; J. Fàbrega; M.A. Fiol 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 638 KB

This paper studies the relation between the connectivity and other parameters of a bipartite (di)graph G. Namely, its order n, minimum degree 6, maximum degree A, diameter D, and a new parameter f related to the number of short paths in G. (When G is a bipartite -undirected --graph this parameter tu

An algorithm for a decomposition of weig

An algorithm for a decomposition of weighted digraphs: with applications to life cycle analysis in ecology

✍ L. Sun; M. Wang 📂 Article 📅 2006 🏛 Springer 🌐 English ⚖ 308 KB

A decomposition for strongly perfect gra

A decomposition for strongly perfect graphs

✍ Stephan Olariu 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 554 KB

A graph G is strongly perfect if every induced subgraph H of G contains a stable set that meets all the maximal cliques of H . We present a graph decomposition that preserves strong perfection: more precisely, a stitch decomposition of a graph G = (V, €1 is a partition of V into nonempty disjoint su

On unavoidable digraphs in orientations

On unavoidable digraphs in orientations of graphs

✍ Gary S. Bloom; Stefan A. Burr 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 480 KB