Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-24T18:16:47.794Z Has data issue: false hasContentIssue false
  • English
  • Français

The Generalisation of Tutte's Result for Chromatic Trees, by Lagrangian Methods

Published online by Cambridge University Press:  20 November 2018

D. M. Jackson  and
I. P. Goulden
D. M. Jackson
Affiliation:
University of Waterloo, Waterloo, Ontario
I. P. Goulden
Affiliation:
University of Waterloo, Waterloo, Ontario
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A K-coloured rooted tree t is said to have colour partitionL if L is a K × ∞ matrix with elements lij equal to the number of non-root vertices of colour i and degree j. If adjacent vertices are of different colours then t is called a chromatic tree and L a chromatic partition. The tree has edge partitionD where D is a K × K matrix with elements dij equal to the number of edges, directed away from the root, from a vertex of colour i to a vertex of colour j.

In this paper we consider a method for enumerating trees with respect to colour and degree information. The method makes use of elementary decompositions of trees, and the functional equations which are induced. A number of new results are obtained by this means. More specifically, we consider (Section 3) the enumeration of rooted plane X-coloured trees with given colour and edge partitions.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 33 , Issue 1 , 01 February 1981 , pp. 12 - 19
Copyright
Copyright © Canadian Mathematical Society 1981

References

1. van Aardenne-Ehrenfest, T. and de Bruijn, N. G., Circuits and trees in oriented graphs, Simon Stevin 28 (1951), 203–217.Google Scholar
2. Brooks, R. L., Smith, C. A. B., Stone, A. H. and Tutte, W. T., The dissection of rectangles into squares, Duke Math. J. 7 (1940), 312–340.Google Scholar
3. Good, I. J., Generalizations to several variables of Lagrange's expansion, with applications to stochastic processes, Proc. Cambridge Phil. Soc. 61 (1965), 499–517.Google Scholar
4. Tutte, W. T., On elementary calculus and the good formula, J. Combinatorial Theory (B) 18 (1975), 97–137.Google Scholar
5. Tutte, W. T., The number of plane planted trees with a given partition, Amer. Math. Monthly 71 (1964), 272–277.Google Scholar
6. Tutte, W. T., The dissection of equilateral triangles into equilateral triangles, Proc. Cambridge Phil. Soc. 44 (1948), 463–482.Google Scholar