|
Математические заметки, 1971, том 9, выпуск 3, страницы 263–273
(Mi mzm9666)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
О числе неизоморфных подграфов в $n$-вершинном графе
А. Д. Коршунов Институт математики Сибирского отделения АН СССР
Аннотация:
Пусть $\mathfrak{G}(n)$ — множество всех неориентированных графов без петель и кратных ребер с $n$ нумерованными вершинами, а $\nu_k(G)$ — число попарно неизоморфных $k$-вершинных подграфов графа $G\in\mathfrak{G}(n)$. Показывается, что не менее $|\mathfrak{G}(n)|(1-1/n)$ графов $G\in\mathfrak{G}(n)$ обладают следующими свойствами: а) при любом $k\in[6\log_2n, cn+5\log_2n]$, где $c=-c\log_2c-(1-c)\times\log_2(1-c)$ и $c>1/2$, $\nu_k(G)>C_n^k(1-1/n^2)$; б) при любом $k\in[cn+5\log_2n, n]$ $\nu_k(G)=C_n^k$. Отсюда следует, что в «почти всех» графах $G\in\mathfrak{G}(n)$ содержится по $\nu(G)\sim2^n$ попарно неизоморфных подграфов. Библ. 1 назв.
Поступило: 18.03.1970
Образец цитирования:
А. Д. Коршунов, “О числе неизоморфных подграфов в $n$-вершинном графе”, Матем. заметки, 9:3 (1971), 263–273; Math. Notes, 9:3 (1971), 155–160
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm9666 https://www.mathnet.ru/rus/mzm/v9/i3/p263
|
Статистика просмотров: |
Страница аннотации: | 365 | PDF полного текста: | 104 | Первая страница: | 1 |
|