Spanning trees and function classes

MaRDI QIDQ698608zbMATH OpenFDO

Authors Jeffrey Remmel, S. Gill Williamson

Publication date 22 September 2002

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/122365, http://www.emis.de/journals/EJC/Volume_9/Abstracts/v9i1r34.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

filtered digraphsoriented spanning forests

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30)

Review text

Summary: If \(G=K_n\) is the complete graph, the classical Prüffer correspondence gives a natural bijection between all spanning trees of \(G\) (i.e., all Cayley trees) and all functions from a set of \(n-2\) elements to a set of \(n\) elements. If \(G\) is a complete multipartite graph, then such bijections have been studied by \textit{Ö. Eğecioğlu} and \textit{J. B. Remmel} [J. Comb. Theory, Ser. A 42, 15-30 (1986; Zbl 0595.05025)]. In this paper, we define a class of directed graphs, called filtered digraphs, and describe a natural class of bijections between oriented spanning forests of these digraphs and associated classes of functions. We derive multivariate generating functions for the oriented spanning forests which arise in this context, and we link basic properties of these spanning forests to properties of the functions to which they correspond. This approach yields a number of new results for directed graphs. Moreover, in the undirected case, various specializations of our multivariate generating function not only include various known results but also give a number of new results.

Recommendations

• scientific article; zbMATH DE number 1424297
• Generalized spanning trees
• Spanning trees and Hamiltonicity
• An Application of Spanning Trees to k -Point Separating Families of Functions
• scientific article; zbMATH DE number 1484041
• Spanning trees of extended graphs
• scientific article; zbMATH DE number 3908451
• Spanning trees and hierarchical networks
• scientific article; zbMATH DE number 4002122
• Tree structures associated to a family of functions

Cited in

(8)

• Factorizations of some weighted spanning tree enumerators
• A CLASS OF GRAPHS WHICH HAS EFFICIENT RANKING AND UNRANKING ALGORITHMS FOR SPANNING TREES AND FORESTS
• Simplicial matrix-tree theorems
• Generating spanning-tree sequences of a fan graph in lexicographic order and ranking/unranking algorithms
• The uncover process for random labeled trees
• A bijective enumeration of labeled trees with given indegree sequence
• Simplicial effective resistance and enumeration of spanning trees
• A weighted cellular matrix-tree theorem, with applications to complete colorful and cubical complexes

This page was built for publication: Spanning trees and function classes

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