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

Дискрет. матем., 2023, том 35, выпуск 4, страницы 46–57 (Mi dm1770)

Масштабирование графов с ограничением диаметра

М. А. Иорданскийab

a Нижегородский государственный университет им. Н. И. Лобачевского
b Нижегородский государственный педагогический университет им. К. Минина

Аннотация: Изучается влияние операций склейки и клонирования подграфов на диаметр графа. Рассматриваются вершинно-диаметральные графы, все вершины которых принадлежат диаметральным цепям, и возможности их использования при масштабировании графов с ограничением диаметра. Приводятся примеры масштабирования деревьев, толстых деревьев и вершинно-диаметральных графов с помощью операций клонирования и склейки. Оценивается диаметр и сложность синтеза таких графов.

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

УДК: 519.175.2

Статья поступила: 16.02.2023

DOI: 10.4213/dm1770



© МИАН, 2024