Premium
On generalized independent subsets of trees
Author(s) -
Drmota Michael,
Kirschenhofer Peter
Publication year - 1991
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240020204
Subject(s) - combinatorics , mathematics , generalization , binary tree , tree (set theory) , random binary tree , natural number , weight balanced tree , plane (geometry) , discrete mathematics , binary search tree , binary number , arithmetic , geometry , mathematical analysis
A natural generalization of the widely discussed independent (or “internally stable”) subsets of graphs is to consider subsets of vertices where no two elements have distance less or equal to a fixed number k (“ k ‐independent subsets”). In this paper we give asymptotic results on the average number of ˆ‐independent subsets for trees of size n , where the trees are taken from a so‐called simply generated family. This covers a lot of interesting examples like binary trees, general planted plane trees, and others.