Том 4, серия 1, номер 1, 1997 г., Стр. 3-12

УДК 519.1
В. Е. Алексеев
О нижних ярусах решетки наследственных классов графов

Аннотация:
Множество обыкновенных графов, замкнутое относительно операции удаления вершин, называется наследственным классом. Исследуется асимптотическое поведение логарифма числа $n$-вершинных графов в бесконечных наследственных классах. Доказано, что эта функция либо растет не медленнее чем $n,\log n$, либо совпадает по порядку с одной из функций 1, $\log n, n$. Охарактеризованы классы, для которых имеет место каждый из этих трех типов поведения.
Библиогр. 5.

Алексеев В. Е. ¹
1. Нижегородский государственный университет,
пр. Гагарина, 23, корп. 2, 603600 Нижний Новгород, ГСП-20, Россия

Статья поступила 24 января 1997 г.