On the number of paths and cycles for almost all graphs and digraphs |
| |
Authors: | I. Tomescu |
| |
Affiliation: | (1) Facultatea de Matematica, Universitatea din Bucureşti, Str. Academiei nr. 14, R-70 109 Bucharest, Romania |
| |
Abstract: | In this paper it is deduced the number ofs-paths (s-cycles) havingk edges in common with a fixeds-path (s-cycle) of the complete graphK n (orK* n for directed graphs). It is also proved that the number of the common edges of twos-path (s-cycles) randomly chosen from the set ofs-paths (s-cycles) ofK n (respectivelyK* n ), are random variables, distributed asymptotically in accordance with the Poisson law whenever s/n exists, thus extending a result by Baróti. Some estimations of the numbers of paths and cycles for almost all graphs and digraphs are made by applying Chebyshev’s inequality. |
| |
Keywords: | 05 C 30 |
本文献已被 SpringerLink 等数据库收录! |
|