• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Locally bounded coverings and factorial properties of graphs

European Journal of Combinatorics. 2012. Vol. 33. No. 4. P. 534-543.
Lozin V. V., Mayhil C., Zamaraev V. A.

Для класса графов X, через Xn обозначается количество графов с множеством вершин {1, . . . , n} из класса X. Класс X называется факториальным, если X – наследственный (т.е. замкнут относительно изоморфизма и операции удаления вершины) и nc1n ≤ Xn ≤ nc2n для некоторых положительных констант c1 и c2. Наследственные классы с субфакториальными функциями числа n-вершинных графов хорошо изучены. Ситуация с факториальными классами существенно сложнее и менее изучена. Хорошо изучены только классы, для которых функция числа n-вершинных растет не быстрее, чем числа Белла. Для того, чтобы лучше понять структуру факториальных классов, мы вводим понятие локально ограниченных покрытий и показываем, что различные классы графов могут быть описаны с помощью этого понятия.