Number of no nisomorphic subgraphs in an n-point graph |
| |
Authors: | A D Korshunov |
| |
Institution: | (1) Mathematics Institute, Siberian Division, Academy of Sciences of the USSR, USSR |
| |
Abstract: | LetG(n) be the set of all nonoriented graphs with n enumerated points without loops or multiple lines, and let vk(G) be the number of mutually nonisomorphic k-point subgraphs of G G(n). It is proved that at least |G(n)| (1–1/n) graphs G G(n) possess the following properties: a) for any k 6log2n], where c=–c log2c–(1–c)×log2(1–c) and c>1/2, we havev
k(G) > C
n
k
(1–1/n2); b) for any k cn + 5 log2n] we havev
k(G) = C
n
k
. Hence almost all graphs G G(n) containv(G) 2n pairwise nonisomorphic subgraphs.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 263–273, March, 1971. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|