scientific article; zbMATH DE number 140084

Publication date 28 March 1993

distribution generating function nodes out-degree random trees

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

[For the entire collection see Zbl 0747.00033.] Let \({\mathcal F}\) denote a simply generated family of rooted trees whose generating function \(y=\Sigma y_ nx^ n\) satisfies a relation of the form \(y=x\Phi(y)\) where \(\Phi(t)=1+\Sigma c_ kt^ k\); if certain conditions are satisfied then \(y_ n\sim c(\Phi(\tau)/\tau)^ nn^{- 3/2}\) where \(\tau\Phi'(\tau)=\Phi(\tau)\). The out-degree of a node \(v\) in a tree \(T_ n\) in \({\mathcal F}\) is the number of edges incident with \(v\) that lead away from the root of \(T_ n\). The distribution of the number \(N_ m=N_ m(T_ n)\) of nodes of out-degree \(m\) in trees \(T_ n\) in \({\mathcal F}\) was investigated in our paper [On nodes of given out-degree in random trees, Combinatories, graphs and complexity, Proc. 4th Czech. Symb., Prachatice/Czech. 1990, Ann. Discrete Math. 51, 213-222 (1992)] for certain ranges of values of \(m\); in particular, if \(m\) is fixed or increases fairly slowly as a function of \(n\), then the distribution of \(N_ m(T_ n)\) is asymptotically normal. Our object here is to investigate the distribution of the number \(J_ m=J_ m(T_ n)\) of nodes of out-degree at least \(m\) when \(m\) increases moderately rapidly as a function of \(n\). In \S2 we review the basic properties of the simply generated families of trees we shall be considering and in \S3 we give some preliminary results of a technical nature. Our main result is in \S4 where we show that if \(m,n\to\infty\) in such a way that \(nr_ m(\tau)/\varphi(\tau)\to\lambda>0\), where \(r_ m(\tau)=\sum^ \infty_ mc_ k\tau^ k\), then \(Pr\{J_ m(T_ n)=j\}\to e^{- \lambda}\lambda^ j/j!\) for each fixed \(j\) as \(m\), \(n\to\infty\). Then in \S5 we strengthen some results in our paper [On the maximum out-degree in random trees, Australas. J. Comb. 2, 147-156 (1990; Zbl 0757.05043)] on the distribution of the maximum out-degree \(\Delta=\Delta(T_ n)\) of nodes in trees \(T_ n\); if \(c_ k>0\) for all \(m\) and \(c_{k+1}/c_ k\to 0\) then \(Pr\{|\Delta-\delta(n)|\leq 1\}\to 1\) as \(n\to\infty\) where \(\delta(n)=\max\{k:nr_ k(\tau)\geq 1\}\). Finally, in \S6 we illustrate these results by giving numerical data on the limiting distribution of \(\Delta(T_ n)\) for two particular families. We remark that the conclusions of some of our results are similar in nature to the conclusions of some results obtained by \textit{B. Bollobás} [Random graphs (1985; Zbl 0567.05042); pp. 56, 62] on node-degrees in random graphs with fixed edge-probability; the underlying problems and the arguments, however, are different.

Recommendations

Cited in

(19)

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 Q4028459)