THE EXFECTED INDEPENDENT DOMINATION NUMBER OF TWO TYPES OF TREES (Q4534322)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1751309
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | THE EXFECTED INDEPENDENT DOMINATION NUMBER OF TWO TYPES OF TREES |
scientific article; zbMATH DE number 1751309 |
Statements
THE EXFECTED INDEPENDENT DOMINATION NUMBER OF TWO TYPES OF TREES (English)
0 references
2 December 2002
0 references
independent domination number
0 references
planted plane trees
0 references
ternary trees
0 references
distance
0 references
generating function
0 references
0 references
0.7722249
0 references
0.76882285
0 references
0.7688112
0 references
0 references
Let \(\mu(n)= \mu_F(n)\) denote the average independent domination number of the \(y_n\) \(n\)-vertex (directed) rooted trees in some family \(F\); we restrict ourselves to values of \(n\) for which such trees exist. Earlier, in [Ars Comb. 56, 201-209 (2000; Zbl 0994.05107)], the author obtained an expression for \(\mu(n)\) as a sum for the family of binary trees. Here he obtains an expression for \(\mu(n)\) as a double sum for the family of planted plane trees, and as the difference of two sums for the family of ternary trees. He concludes that \(\mu(n)\sim n/2\) for all three families by, in effect, misapplying a result of Schur [cf. \textit{G. Pólya} and \textit{G. Szegö}, Problems and theorems in analysis. I. (Springer, Berlin) (1972; Zbl 0236.00005), p. 39, exer. 178]; Schur's result requires that two functions have a difference radius of convergence, a condition not satisfied here. The independent domination number of a (directed) rooted tree is the same as the number of vertices at even distance from the root. If \(F\) is any simply generated family of trees whose generating function \(y= y(x)\) satisfies a relation of the form \(y= x\Phi(y)\), then it follows from Theorem 4.1 in \textit{A. Meir} and \textit{J. W. Moon} [Can. J. Math. 30, 997-1015 (1978; Zbl 0394.05015)] that the generating function for the numbers \(\mu(n)y_n\) is given by \({1\over 2} xy'+{1\over 2}y(1+ x\Phi'(y))^{-1}\). Hence \(\mu(n)\sim n/2\) for any such family \(L\), by Darboux's method, if some mild technical assmptions hold. The analogous result for the corresponding family \(G\) of planted trees follows from the fact that \(\mu_G(n+ 1)= n+1-\mu_F(n)\). So the problems for the binary and the ternary trees are, in effect, the same problem. And \(\mu(n)= n/2\) for the family of plane trees if \(n\geq 2\); so the double sum expression mentioned for \(\mu(n)\) for the planted plane trees is in fact equal to \((n+1)/2\) if \(n\geq 3\).
0 references