Locally bounded coverings and factorial properties of graphs

European Journal of Combinatorics. 2012. Vol. 33. No. 4. P. 534–543.

Лозин В. В., Мэйхил К., Замараев В. А.

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

Ключевые слова: hereditary class of graphs, speed of hereditary properties, factorial class, наследственный класс графов, факториальный класс