RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., сер. 1, 2001, том 8, выпуск 3, страницы 73–80 (Mi da226)

Об изометрическом вложении произвольных графов в графы заданного диаметра, обладающие свойством продолжения метрики

В. А. Ташкинов

Институт математики им. С. Л. Соболева СО РАН

Аннотация: Доказывается, что произвольный обыкновенный граф $G$ можно вложить как порожденный подграф в граф $H$ заданного диаметра $d(H)=d\geqslant 2$, в котором любые две вершины лежат на некоторой диаметральной цепи. При этом если диаметр $d(G)$ графа $G$ не превосходит $d$, то вложение может быть осуществлено изометрически, т.е. с сохранением расстояний между вершинами в $G$. Ил. 1, библиогр. 4.

УДК: 519.176

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



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


© МИАН, 2024