|
Прикладная теория графов
О минимальных вершинных $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$-расширение, вершинная отказоустойчивая реализация, ориентация цепи.
Образец цитирования:
М. Б. Абросимов, О. В. Моденова, “О минимальных вершинных $1$-расширениях ориентаций цепей”, ПДМ, 2017, № 38, 89–94
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm601 https://www.mathnet.ru/rus/pdm/y2017/i4/p89
|
Статистика просмотров: |
Страница аннотации: | 147 | PDF полного текста: | 39 | Список литературы: | 37 |
|