About the number of vines and regular vines on n nodes
O. Morales Napoles
R.M. Cooke
D. Kurowicka
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The theory of graphs is important not only for combinatorial problems but in physics, electrical engineering, chemistry, social psychology, and research of operations. Labeled trees find application in probability theory. These objects were first successfully counted by Cayley in 1889. Vines generalize trees. They were introduced by Cooke in 1997 and they have been applied in uncertainty analysis. More recently applications in statistics have been developed in which distinguishing vines according to their graphical structure is of importance [1], [2], [3], [4], [5]. In this paper, previous results about the number of labeled trees on n nodes will be discussed. Some of the ideas previously used to characterize trees will be extended to characterize vines on n nodes. Algorithms to build vines, together with a result about the number of vines on n nodes will be presented.