publication . Article . 1986

Bijections for Cayley trees, spanning trees, and their q -analogues

Eǧecioǧlu, Ömer; Remmel, Jeffrey B;
Open Access
  • Published: 01 May 1986 Journal: Journal of Combinatorial Theory, Series A, volume 42, pages 15-30 (issn: 0097-3165, Copyright policy)
  • Publisher: Elsevier BV
Abstract
AbstractWe construct a family of extremely simple bijections that yield Cayley's famous formula for counting trees. The weight preserving properties of these bijections furnish a number of multivariate generating functions for weighted Cayley trees. Essentially the same idea is used to derive bijective proofs and q-analogues for the number of spanning trees of other graphs, including the complete bipartite and complete tripartite graphs. These bijections also allow the calculation of explicit formulas for the expected number of various statistics on Cayley trees.
Subjects
arXiv: Mathematics::Combinatorics
free text keywords: Graph theory, Generating function, Bijection, Discrete mathematics, Cayley graph, Bipartite graph, Bijection, injection and surjection, Tree (graph theory), Spanning tree, Combinatorics, Mathematics, Theoretical Computer Science, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics
Related Organizations
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue