"Записки научных семинаров ПОМИ"
Том 554, стр. 25-53
Графы с максимальным цепным индексом и их свойства
А. Э. Гутерман, С. А. Жилина, Е. Р. Шафеев
Университет Бар-Илан, Рамат-Ган, 5290002, Израиль
alexander.guterman@biu.ac.il
Московский государственный университет имени М.В. Ломоносова, Москва, 119991, Россия;
Московский центр фундаментальной и прикладной математики, Москва, 119991, Россия
s.a.zhilina@gmail.com
shafeev.ev@yandex.ru
- Аннотация:
В работе получено полное описание множества графов с максимальным
цепным индексом. В частности, показано, что такие графы имеют
строгие ограничения на количество рёбер и степени вершин.
Более того, графы с максимальным цепным индексом образуют пять
параметрических семейств, одно из которых состоит из графов,
не являющихся сильно связными. Как следствие, вычислено число
графов на $n$ вершинах, имеющих максимальный цепной индекс,
а также получены значения примитивной экспоненты для этих графов.
Библ. -- 13 назв.
- Ключевые слова: цепные матрицы, цепной индекс,
неотрицательные матрицы
[chainable matrices, chainable index, nonnegative matrices]
Полный текст(.pdf)