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

Статья

On factorial properties of chordal bipartite graphs

Discrete Mathematics. 2012. Vol. 312. No. 16. P. 2457-2465.
Lozin V. V., Dabrowski K., Zamaraev V. A.

Для класса графов X через Xn обозначается количество графов с множеством вершин {1, . . . , n} из класса X. Класс X называется факториальным, если X – наследственный (т.е. замкнут относительно изоморфизма и операции удаления вершины) и nc1n ≤ Xn ≤ nc2n для некоторых положительных констант c1 и c2. Наследственные классы с субфакториальными функциями числа n-вершинных графов хорошо изучены. Ситуация с факториальными классами существенно сложнее и менее изучена. В качестве одного из подходов к исследованию факториальных классов, в данной работе рассматриваются минимальные сверхфакториальные классы. В [J.P. Spinrad, Nonredundant 1's in Γ-free matrices, SIAM Journal on Discrete Mathematics,  8 (1995) 251--257], Спинрад показал, что число n-вершинных хордальных двудольных графов равно 2Θ(n log2n), то есть данный класс – сверхфакториальный. С другой стороны, все известные из литературы наследственные подклассы класса хордальных двудольных графов являются факториальными. Помимо лесов, к ним, в частности, относятся двудольные перестановочные графы, двудольные вполне сепарабельные графы, выпуклые графы. В данной работе изучаются новые наследственные подклассы класса хордальных двудольных графов и среди них выявляются как факториальные, так и сверхфакториальные. Последний результат показывает, что класс хордальных двудольных графов не является минимальным сверхфакториальным. Поиск минимальных сверхфакториальных подклассов класса хордальных двудольных графов остается открытым вопросом.