Spanning trees and function classes
type: Item
instance of: scholarly article
title: Spanning trees and function classes
zbMATH Open document ID: 1005.05015
author: Jeffrey Remmel
author: S. Gill Williamson
published in: The Electronic Journal of Combinatorics
publication date: 2002-09-22T00:00:00Z
full work available at URL: https://eudml.org/doc/122365
full work available at URL: v9i1r34.html
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.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 1803671
zbMATH Keywords: filtered digraphs
zbMATH Keywords: oriented spanning forests
MaRDI profile type: Publication
Recommended article: Q4945509
Recommended article: Generalized spanning trees
Recommended article: Q5133202
Recommended article: An Application of Spanning Trees to k -Point Separating Families of Functions
Recommended article: Q4493158
Recommended article: Spanning trees of extended graphs
Recommended article: Q3686729
Recommended article: Q4925718
Recommended article: Q3754636
Recommended article: Tree structures associated to a family of functions
description: scientific article; zbMATH DE number 1803671