On the asymptotic behavior of the independence number of a random \((n,n)\)-tree
type: Item
instance of: scholarly article
title: On the asymptotic behavior of the independence number of a random \((n,n)\)-tree
zbMATH Open document ID: 0845.05081
DOI: 10.1007/BF01858439
author: Yanyan Li
published in: Graphs and Combinatorics
publication date: 1996-08-26T00:00:00Z
review text: Let \(T\) denote a bipartite tree with \(n\) labelled dark nodes and \(n\) labelled light nodes. The authors show that the node independence number of \(T\) lies between \(n\) and \((1.27974)n\) for almost all such trees \(T\) as \(n \to \infty\).
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 867721
zbMATH Keywords: asymptotic behavior
zbMATH Keywords: random
zbMATH Keywords: bipartite tree
zbMATH Keywords: node independence number
reviewed by: J. W. Moon
MaRDI profile type: Publication
cites work: Asymptotic Methods in Enumeration
cites work: Q3682518
cites work: On the expected number of edges in a maximum matching of an (r,s)-tree
cites work: Some remarks on the theory of graphs
cites work: Q3270978
cites work: On Representatives of Subsets
cites work: Another Enumeration of Trees
cites work: Q5616724
cites work: Matchings in random superpositions of bipartite trees
full work available at URL: https://doi.org/10.1007/bf01858439
OpenAlex ID: W2011566902
Recommended article: On the independence number of some random trees
Recommended article: Q4882025
Recommended article: On the \(k\)-component independence number of a tree
Recommended article: Q4552229
Recommended article: A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
Recommended article: On the number of independent sets in a tree
Recommended article: Asymptotically independent topological indices on random trees
Recommended article: On the spectral radius of trees with given independence number
Recommended article: THE EXPECTED INDEPENDENT DOMINATION NUMBER OF RANDOM DIRECTED ROOTED TREES
Recommended article: Q3115728
description: scientific article; zbMATH DE number 867721