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

ПДМ, 2017, номер 38, страницы 89–94 (Mi pdm601)

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

О минимальных вершинных $1$-расширениях ориентаций цепей

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

a Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского, г. Саратов, Россия
b Научно-образовательный центр "Эрудит", г. Саратов, Россия

Аннотация: Исследуются верхняя и нижняя оценки числа дополнительных дуг $ec(P_n)$ минимального вершинного $1$-расширения ориентации цепи $P_n$. Если ориентация цепи $\overrightarrow P_n$ имеет концы разного типа и отлична от гамильтоновой, то $\lceil({n+1})/6\rceil+2\leq ec(P_n)\leq n+3$. Если ориентация цепи $\overrightarrow P_n$ имеет концы одинакового типа, то $\lceil({n+1})/4\rceil+2\leq ec(P_n)\leq n+3$.

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

УДК: 519.17

DOI: 10.17223/20710410/38/6



Реферативные базы данных:


© МИАН, 2024