RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика. Приложение // Архив

ПДМ. Приложение, 2016, выпуск 9, страницы 101–102 (Mi pdma289)

Прикладная теория автоматов и графов

Уточнение нижней оценки числа дополнительных дуг минимального вершинного $1$-расширения ориентации цепи

М. Б. Абросимов, О. В. Моденова

Саратовский государственный университет имени Н. Г. Чернышевского, г. Саратов

Аннотация: Ранее был получен следующий результат: минимальное вершинное $1$-расширение любой отличной от гамильтоновой ориентации цепи с числом вершин больше 4 содержит по крайней мере четыре дополнительные дуги. В данной работе удалось значительно уточнить эту оценку, а также получить верхнюю оценку на число дополнительных дуг.

Ключевые слова: минимальное вершинное $1$-расширение, ориентация цепи, отказоустойчивость.

УДК: 519.17

DOI: 10.17223/2226308X/9/39



© МИАН, 2024