Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Spanning Trees and Function Classes"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Spanning Trees and Function Classes. | Spanning Trees and Function Classes Jeffery B. Remmel Department of Mathematics U.C.S.D. La Jolla CA 92093-0112 jremmel@ucsd.edu S. Gill Williamson Department of Computer Science and Engineering U.C.S.D. La Jolla CA 92093-0114 gwilliamson@ucsd.edu Submitted September 17 2001 Accepted August 12 2002 MR Subject Classifications 05A15 05C05 05C20 05C30 Abstract If G Kn is the complete graph the classical Pruffer 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 Egecioglu and Remmel. 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. 1 Introduction This paper is motivated by the work of Egecioglu and Remmel 4 who gave a bijective proof of the formula nn-2 for the number of Cayley trees on n vertices i.e. the number of spanning trees of the complete graph Kn. In particular they showed that there is a natural bijection between the set of Cn 1 of all Cayley trees on n vertices where all edges are directed toward the root 1 and the class of functions F f 2 . n 1 1 . n . Later in 5 Egecioglu and Remmel extended this idea to give a bijective proof for the number of spanning trees of the complete fc-partite graph Kni nk. Again in 5 Egecioglu THE ELECTRONIC JOURNAL OF COMBINATORICS 9