scientific article; zbMATH DE number 1792637
The independent domination number \(\alpha '(D)\) of a digraph \(D=(V,E)\) is the minimum cardinality of a set \(X\subset V\) such that (i) \(xy\in E\) for no \(x,y\in X\) and (ii) for every \(y\in V\backslash X\) there exists \(x\in X\) for which \(xy\in E\). Binary trees are rooted directed plane trees in which every vertex has 0 or 2 children. It is well known that the set \({\mathcal T}_n\) of binary trees with \(2n+1\) vertices has \(t_n={2n\choose n}/(n+1)\) elements. The author proves that the expected value \(\mu (2n+1)\) of \(\alpha '(T)\) over \({\mathcal T}_n\) is \(\sum (k+1)2^k(n)_k/(2n)_k\) and that \(\mu (2n+1)/(2n+1)\rightarrow 1/2\). Here \((n)_k=n(n-1)\cdots (n-k+1)\) and \(\sum \) runs over even \(k\) with \(0\leq k\leq n\). The formula \[ \sum _{n\geq 0}\mu (2n+1)t_nx^{2n+1}= 2x\cdot (1-4x^2)^{-1/2}\cdot (1+(1-4x^2)^{1/2})^{-1}\cdot (2-(1-4x^2)^{1/2})^{-1} \] is derived.
- THE EXPECTED INDEPENDENT DOMINATION NUMBER OF RANDOM DIRECTED ROOTED TREES
- THE EXFECTED INDEPENDENT DOMINATION NUMBER OF TWO TYPES OF TREES
- Comment on ``The expectation of independent domination number over random binary trees
- On the independence number of some random trees
- A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
- On the asymptotic behavior of the independence number of a random (n,n)-tree
- The ratio of domination and independent domination numbers on trees
- The Expected Distribution of Degrees in Random Binary Search Trees
- Domination, independent domination and \(k\)-independence in trees
- scientific article; zbMATH DE number 2230941
- On the asymptotic behavior of the independence number of a random (n,n)-tree
- On the independence number of some random trees
- Comment on ``The expectation of independent domination number over random binary trees
- THE EXFECTED INDEPENDENT DOMINATION NUMBER OF TWO TYPES OF TREES
- THE EXPECTED INDEPENDENT DOMINATION NUMBER OF RANDOM DIRECTED ROOTED TREES
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4552229)