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

ПДМ, 2016, номер 2(32), страницы 115–118 (Mi pdm548)

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

О количестве шпернеровых вершин в дереве

В. Н. Салий

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

Аннотация: Вершина $v$ дерева $T$ называется шпернеровой вершиной, если входящее дерево $T(v)$, полученное из $T$ ориентацией всех рёбер в направлении к $v$, обладает шпернеровым свойством: в нём среди наибольших (по числу элементов) подмножеств, состоящих из попарно недостижимых вершин, по крайней мере в одном все вершины равноудалены от $v$. Приводятся явные способы подсчёта количества шпернеровых вершин в деревьях некоторых типов.

Ключевые слова: дерево, шпернерова вершина, цепь, звезда, пальма, шеренга, гусеница, кортеж пальм.

УДК: 519.17

DOI: 10.17223/20710410/32/8



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


© МИАН, 2024